A Combination of Berry Ravindran Algorithm and Two Way Algorithm for Exact String Matching

[[abstract]]精確字?比對問題定義如下：給予一個長?為 的字? ，長?為 的字? 我們的目標是要在T 上找出所有 發生的位置。對於電腦科學而言，字串比對問題是一個重要的議題。 在本篇論文中，我們提出一個新的方法來解決這個問題. Two Way 演算法與Berry Ravindran 演算法在找尋在 上找出所有 發生的位置而言都是很好的演算法, 不過仍然存在著一些問題. 如果我們考慮在Window後面的兩個字元與P最右邊的兩個字元相等的情形,那麼Berry Ravindran 演算法就會沒有效率.如果我們把 分成 跟 兩部份,常常在 部份就發生錯誤,那麼Two Way 演算法也沒有效率.所以我們把兩個演算法結合起來來解決精確字串比對問題. 最後, 我們會討論Two Way 演算法、Berry Ravindran演算法跟我們的方法 關鍵字：精確字串比對問題、Two Way 演算法、Berry Ravindran 演算法[[abstract]]The exact string matching problem is defined as follows: We are given a text and a pattern , . Our purpose is to find all occurrences of in . It is a classical and important problem in computer science. In this thesis, we propose a new approach to solve this problem. Two Way algorithm and the Berry Ravindran algorithm are good algorithms which find all occurrences of in , but some problems still exist. If we consider the situation that the last two text characters of the window with size m are the same with that of , Berry Ravindran algorithm is not efficient in this situation. If a mismatch often occurs within v part of , Two Way algorithm is not efficient in this situation. So we combine Two Way algorithm and Berry Ravindran algorithm to slove this problem Finally; we discuss the results of Two Way algorithm, Berry Ravindran algorithm and our approach. Keywords：Exact String Matching、Two Way algorithm、Berry Ravindran algorithm[[note]]碩