我們對數種常見的字串比較演算法做實驗模擬，分析研究各種演算法所需的工作效能。同時，進一步詳細探討波以爾莫爾演算法及其衍生相關演算法所需之工作量，包含比較次數和執行時間。

In this thesis, we give experimental results on the performance of several popular string-matching algorithms. Meanwhile the behaviors of the costs of some variant Boyer-Moore algorithms are investigated. The costs considered include the numbers of character inspections, and the total time used.

Contents
1 Introduction 1
2 The String-Matching Algorithms 5
2.1 Knuth-Morris-Pratt Algorithm . . . . . . . . . . . . . . 5
2.1.1 KMP shift rule . . . . . . . . . . . . . . . . . . 6
2.2 Karp-Rabin Algorithm . . . . . . . . . . . . . . . . . . 9
2.2.1 KR shift rule . . . . . . . . . . . . . . . . . . . 10
2.3 Shift-Or Algorithm . . . . . . . . . . . . . . . . . . . . 11
2.3.1 SO shift rule . . . . . . . . . . . . . . . . . . . . 12
2.4 Boyer-Moore Algorithm . . . . . . . . . . . . . . . . . 15
2.4.1 Right-to-left scan . . . . . . . . . . . . . . . . . 17
2.4.2 DELTA 1 : Bad character shift . . . . . . . . . 18
2.4.3 DELTA 2 : Good sux shift . . . . . . . . . . . 19
2.5 Comparisons . . . . . . . . . . . . . . . . . . . . . . . . 21
3 Variants of the BM Algorithm 28
3.1 Turbo BM Algorithm . . . . . . . . . . . . . . . . . . . 28
3.2 Tuned BM Algorithm . . . . . . . . . . . . . . . . . . . 31
3.3 Horspool Algorithm . . . . . . . . . . . . . . . . . . . . 33
3.4 Sunday Algorithm . . . . . . . . . . . . . . . . . . . . 34
3.5 Comparisons . . . . . . . . . . . . . . . . . . . . . . . . 35
4 Conclusions 50

Bibliography
[1] A. V. Aho, M. J. Corasick, 1975, Ecient String Matching: An
aid to bibliographic search. Communications of the ACM, 18(4),
pp.333-340.
[2] A. APOSTOLICO, R. GIANCARLO, 1986, The Boyer-Moore-
Galil string searching strategies revisited, SIAM Journal on Com-
puting, 15(1), pp.98-105.
[3] R. A. BAEZA-YATES, G. H. GONNET, 1992, A new approach
to text searching, it Communications of the ACM. 35(10), pp.74-
82.
[4] R. S. BOYER, J. S. MOORE., 1977, A fast string searching al-
gorithm. Communications of the ACM. 20, pp.762-772.
[5] M. CROCHEMORE, A. CZUMAJ, L. GASIENIEC, S.
JAROMINEK, T. LECROQ, W. PLANDOWSKI, W.RYTTER,
1992, Deux methodes pour accelerer l'algorithme de Boyer-
Moore, in Theorie des Automates et Applications, Actes des 2e
Journees Franco-Belges, D. Krob ed., Rouen, France, 1991, pp
45-63, PUR 176, Rouen, France.
[6] M. CROCHEMORE, D. PERRIN, 1991, Two-way string-
matching, Journal of the ACM, 38(3), pp.651-675.
[7] R. COLE, 1994, Tight bounds on the complexity of the Boyer-
Moore pattern matching algorithm, SIAM Journal on Computing,
23(5), pp.1075-1091.
[8] L. COLUSSI, 1994, Fastest pattern matching in strings, Journal
of Algorithms, 16(2), pp.163-189.
[9] L. J. Guibas, A. M. Odlyzko, 1980, A new proof of the linearity
of the Boyer-Moore string searching algorithm, SIAM Journal on
Computing, 9(4), pp.672-682.
[10] R. N. HORSPOOL, 1980, Practical fast searching in strings, Soft-
ware - Practice and Experience, 10(6), pp.501-506.
[11] A. HUME and D. M. SUNDAY , 1991, Fast string searching,
Software - Practice and Experience, 21(11), pp.1221-1248.
[12] D. E. KNUTH, J. H. MORRIS (Jr), PRATT V.R., 1977, Fast
pattern matching in strings, SIAM Journal on Computing, 6(1),
pp.323-350.
[13] R. M. KARP, M. O. RABIN, 1987, Ecient randomized pattern-
matching algorithms. IBM J. Res. Dev, 31(2), pp.249-260.
[14] J. H. MORRIS (Jr), V. R. PRATT, 1970, A linear pattern-
matching algorithm, Technical Report 40, University of Califor-
nia, Berkeley.
[15] D. M. SUNDAY, 1990, A very fast substring search algorithm,
Communications of the ACM, 33(8), pp.132-142.