精確字串比對問題定義如下：給予一個長度為 的字串 ，長度為 的字串 我們的目標是要在T 上找出所有 發生的位置。對於電腦科學而言，字串比對問題是一個重要的議題。
在本篇論文中，我們提出一個新的方法來解決這個問題. Two Way 演算法與Berry Ravindran 演算法在找尋在 上找出所有 發生的位置而言都是很好的演算法, 不過仍然存在著一些問題. 如果我們考慮在Window後面的兩個字元與P最右邊的兩個字元相等的情形,那麼Berry Ravindran 演算法就會沒有效率.如果我們把 分成 跟 兩部份,常常在 部份就發生錯誤,那麼Two Way 演算法也沒有效率.所以我們把兩個演算法結合起來來解決精確字串比對問題.

最後, 我們會討論Two Way 演算法、Berry Ravindran演算法跟我們的方法

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.

Contents

Chapter 1 Introduction………………………………………………………………1


1.1 Motivations………………………………………………………………………..1

1.2 Previous Works……………………………………………………………………1

1.3 Thesis Organization……………………………………………………………….2


Chapter 2 Reviews and Basic Algorithm…………………………………………..3


2.1 The Basic Terminologies of Strings………………………………………...……3


2.2 The Brute-Force Algorithm………………………………………………………5


2.3 Two Way Algorithm……………………………………………………………...6

2.3.1 The Terminologies in the Two Way Algorithm…………………………….6

2.3.1.1 Short Maximal Suffix……………………………………………….6

2.3.1.2 The Non-Overlapping Property of Maximal Suffix………………...7

2.3.2 The Two Way Algorithm with Short Maximal Suffix……………………...8

2.4 Berry Ravindran Algorithm………………………………………………………14

2.4.1 Idea…………………………………………………………………………14

2.4.2 Preprocessing Phase………………………………………………………..21

2.4.3 Full Example……………………………………………………………….23





Chapter 3 Our Faster algorithm………………………………………………….26


3.1 Our Algorithms……………………………………………………………….…26

3.1.1 Preprocessing Phase……………………………………………………….28

3.1.2 Searching Phase……………………………………………………….…..29

3.1.3 Full Example………………………………………………………………31
.

Chapter 4 Experimental Result…………………………………………………...32



Chapter 5 Conclusion……………………………………………………………...33


Bibliography……………………………………………………………………..…34

Bibliography


[BM77] A Fast String Searching Algorithm, Boyer, R. S. and Moore, J. S.,Communication of the ACM, Vol. 20, 1977, pp. 762-772.

[KMP77] Fast pattern matching in strings, KNUTH D.E., MORRIS (Jr) J.H., PRATT V.R. SIAM Journal on Computing 6(1), 1977, pp.323-350


[C89] String Matching and Periods, Crochemore, M., Theoretical Computer Science, Vol.39, 1989, pp. 149-153.

[S90] A very fast substring search algorithm, SUNDAY D.M., Communications of the ACM .1990, pp. 132-142.

[CLP98] Very Fast String Matching Algorithm for Small Alphabets and Long Patterns, Christian, C., Thierry, L. and Joseph, D.P., Lecture Notes in Computer Science, Vol. 1448, 1998, pp. 55-64

[BR99] Proceedings of the Prague Stringology Club Workshop ’99, Prague, Czech Republic, pp.16-28.

[CP91] Two-Way String Matching, Crochemore, M. and Perrin, D., Journal of ACM, Vol.38(3), 1991, pp.651-675.

[CR2002] Jewels of Stringology, Crochemore, M. and Rytter, W., World Scientific, Singapore, 2002.


[CR94] Text Algorithms, Crochemore, M. and Rytter, W., Oxford University Press, 1994.
[L2001] Computational Biology, Lee, R. C. T., 2001.

[LTCT2005] Introduction to the Design and Analysis of Algorithms, Lee, R. C. T., Tseng,S. S., Chang, R. C., Tsai, Y. T., McGraw-Hill Education(Asia), 2005.

[R89] Knuth-Morris-Pratt Algorithm: an Analysis, Régnier, M., In Proceedings of the 14thSymposium on Mathematical Foundations of Computer Science, number 397 in LectureNotes in Computer Science, 1989, pp.431-444.