文档介绍：Pattern matching and pression algorithms
Maxime Crochemore 1 Thierry Lecroq 2
1Institut Gaspard Monge, Universite´ de Marne la Valle´e, 2 rue de la Butte Verte, F-93166 Noisy-le-Grand
Cedex, France, e-mail: ******@univ-
2Laboratoire d’Informatique de Rouen, Universite´ de Rouen, Faculte´s des Sciences et Techniques, F-76821
Mont-Saint-Aignan Cedex, France, e-mail: ******@-
Contents
1 Processing texts efficiently 5
2 String-matching algorithms 6
Karp-Rabin algorithm
6
Knuth-Morris-Pratt algorithm
7
Boyer-Moore algorithm
9
Quick Search algorithm
12
Experimental results
13
Aho-Corasick algorithm
14
3 Two-dimensional pattern matching algorithms 20
Zhu-Takaoka algorithm
20
Bird/Baker algorithm
21
4 Suffix trees 26
McCreight algorithm
28
5 mon subsequence of two strings 33
Dynamic programming
33
Reducing the space: Hirschberg algorithm
34
6 Approximate string matching 38
Shift-Or algorithm
38
String matching with k mismatches 40
String matching with k differences 41
Wu-Manber algorithm
43
7 pression 45
Huffman coding
45
Encoding
46
Decoding
53
pression
53
method
55
pression method
55
Implementation