臺灣博碩士論文加值系統

在這篇論文裡，我們討論如何解決完整字串比對問題。 字串比對問題是要在字串T中，找出所有字串P發生的位置。 一般的字串比對演算法在線性時間及線性空間完成，其中最有名的為Kunth-Morris-Pratt演算法及Boyer-Moore演算法。 而我們將利用雜湊的結構來解決完整字串比對。 我們的演算法很容易實做，並將此演算法工作在常數空間。而且經過實驗，我們的演算法優於暴力法以及kunth-Morris-Pratt演算法。

In this thesis, we consider how to solve the exact string matching problem. The exact string matching problem is to find all locations of a pattern string P in a text string T. In general, string matching algorithm problem work in linear time and linear space. The two well-known of them are Knuth-Morris-Pratt (KMP) algorithm and Boyer-Moore (BM) algorithm. We will use the hashing scheme to solve the exact string matching problem. Our method is simple to implement, and our algorithm work in constant space. Experimental shows that our algorithm is better than Brute Force algorithm and KMP algorithm.

Chapter 1 Introduction 1
1.1 Motivations 1
1.2 Thesis Organization 1
Chapter 2 Reviews and Basic Algorithms 2
2.1 Basic Terminologies of Strings 2
2.2 Brute force algorithm 3
2.3 The KMP algorithm 5
2.3.1 A Full Example of KMP Algorithm 12
2.4 The Boyer-Moore Algorithm 15
Chapter 3 An Exact String Matching Algorithm Using Hashing Scheme 24
3.1 Term Definitions 24
3.2 Algorithm-Finding Exact String Matching Using Hashing 26
3.2.1 A Full Example of Finding Exact String Matching Using Hashing 29
3.3 Experiment 35
3.3.1 Long Pattern 35
3.3.2 Short Pattern 37
Chapter 4 Conclusion 39
Bibliography 40

[AC91] Optimal canonization of all substrings of a string, Apostolico, A. and Crochemore, M., Information and Computation, Vol. 95, 1991, pp. 76-95.

[AG86] The Boyer-Moore-Galil string searching strategies revisited, Apostolico, A. and Giancarlo, R., SIAM Journal on Computing, Vol. 15, 1986, pp. 98-105.

[BM77] A fast string searching algorithm, Boyer, R.S. and Moore, J.S., Communications of the ACM, Vol. 20, 1977, pp. 762-772.

[C91] Correctness and efficiency of the pattern matching algorithms, Colussi, L., Information and Computation, Vol. 95, No. 2, 1991, pp. 225-251.

[C94] Fastest pattern matching in strings, Colussi, L., Journal of Algorithms, Vol. 16, No. 2, 1994, pp. 163-189.

[CCGJLPR92] Deux méthodes pour accélérer l'algorithme de Boyer-Moore, Crochemore, M., Czumaj, A., Gasieniec, L., Jarominek, S., Lecroq, T., Plandowski, W. and Rytter, W., in Théorie des Automates et Applications, Actes des 2e Journées Franco-Belges, D. Krob ed., Rouen, France, 1992, pp. 45-63, PUR 176, Rouen, France.

[CLP98] A very fast string matching algorithm for small alphabets and long patterns, in Proceedings of the 9th Annual Symposium on Combinatorial Pattern Matching , Charras, C., Lecroq, T. and Pehoushek, J.D., M. Farach-Colton ed., Piscataway, New Jersey, Lecture Notes in Computer Science 1448, 1998, pp. 55-64, Springer-Verlag, Berlin.

[GG92] On the exact complexity of string matching: upper bounds, Galil, Z. and Giancarlo, R., SIAM Journal on Computing, Vol. 21, No. 3, 1992, pp. 407-437.

[GS83] Time-space optimal string matching, Galil, Z. and Seiferas, J., Journal of Computer and System Science, Vol. 26, No.3, 1983, pp. 280-294.

[H80] Practical fast searching in strings, Horspool, R.N., Software - Practice & Experience, Vol. 10, No. 6, 1980, pp. 501-506.

[KMP77] Fast pattern matching in strings, Knuth, D.E., Morris (Jr), J.H. and Pratt, V.R., SIAM Journal on Computing, Vol. 6, No. 2, 1977, pp. 323-350.

[L92] A variation on the Boyer-Moore algorithm, Lecroq, T., Theoretical Computer Science, Vol. 92, No. 1, 1992, pp. 119-144.

[MP70]: A linear pattern-matching algorithm, Morris (Jr), J.H. and Pratt, V.R., Technical Report 40, 1970, University of California, Berkeley.

[R2003]On Maximal Suffixes and Constant-Space Linear-Time Versions of KMP Algorithm, Rytter, W., Theoretical Computer Science, Vol. 299(1-3), 2003, pp. 763-774.

[S90] A very fast substring search algorithm, Sunday, D.M., Communications of the ACM, Vol. 33, No. 8, 1990, pp. 132-142.

[S93] String matching algorithms and automata, Simon, I., in Proceedings of 1st American Workshop on String Processing, R.A. Baeza-Yates and N. Ziviani ed., 1993, pp. 151-157, Universidade Federal de Minas Gerais, Brazil.