Computing Patterns in Strings

Cover......Page __sk_0000.djvu
Copyright......Page __sk_0002.djvu
Contents......Page __sk_0003.djvu
Preface......Page __sk_0007.djvu
Part I. Strings and Algorithms......Page __sk_0013.djvu
1.1 Strings of Pearls......Page __sk_0015.djvu
1.2 Linear Strings......Page __sk_0017.djvu
1.3 Periodicity......Page __sk_0026.djvu
1.4 Necklaces......Page __sk_0037.djvu
2.1 Intrinsic Patterns (Part II)......Page __sk_0047.djvu
2.2 Specific Patterns (Part III)......Page __sk_0053.djvu
2.3 Generic Patterns (Part IV)......Page __sk_0063.djvu
3.1 Avoidance Problems and Morphisms......Page __sk_0073.djvu
3.2 Tbue Strings (2,3)......Page __sk_0077.djvu
3.3 Thue Strings (3, 2)......Page __sk_0084.djvu
3.4 Fibostrings (2,4)......Page __sk_0088.djvu
4.1 Good Algorithms......Page __sk_0101.djvu
4.2 Distinct Patterns......Page __sk_0106.djvu
4.3 Distinct Borders......Page __sk_0112.djvu
Part II. Computing Intrinsic Patterns......Page __sk_0121.djvu
5.1 Border Trees......Page __sk_0123.djvu
5.2 Suffix Trees......Page __sk_0125.djvu
5.2.1 Preliminaries......Page __sk_0126.djvu
5.2.2 McCreight\'s Algorithm......Page __sk_0129.djvu
5.2.3 Ukkonen\'s Algorithm......Page __sk_0133.djvu
5.2.4 Farach\'s Algorithm......Page __sk_0138.djvu
5.2.5 Application and Implementation......Page __sk_0149.djvu
5.3.1 Directed Acyclic Word Graphs......Page __sk_0152.djvu
5.3.2 Suffix Arrays -- Saving the Best till Last?......Page __sk_0161.djvu
6. Decomposing a String......Page __sk_0169.djvu
6.1 Lyndon Decomposition: Duval\'s Algorithm......Page __sk_0170.djvu
6.2 Lyndon Applications......Page __sk_0179.djvu
6.3 s-Factorization: Lempel-Ziv......Page __sk_0187.djvu
Part III. Computing Specific Patterns......Page __sk_0191.djvu
7.1 Knuth-Moms-Pratt......Page __sk_0193.djvu
7.2 Boyer-Moore......Page __sk_0199.djvu
7.3 Karp-Rabin......Page __sk_0210.djvu
7.4 Domolki-(Baeza-¥ates)-Gonnet......Page __sk_0214.djvu
7.5 Summary......Page __sk_0218.djvu
8. Son of BM Rides Again!......Page __sk_0219.djvu
8.1 The BM Skip Loop......Page __sk_0220.djvu
8.2 BM-Horspool......Page __sk_0222.djvu
8.3 Frequency Considerations and BM-Sunday......Page __sk_0224.djvu
8.4 BM-Galil......Page __sk_0231.djvu
8.5 Turbo-BM......Page __sk_0235.djvu
8.6 Daughter of KMP Rides Too!......Page __sk_0238.djvu
8.7 Mix Your Own Algorithm......Page __sk_0243.djvu
8.8 The Exact Complexity of Exact Pattern-Matching......Page __sk_0245.djvu
9. String Distance Algorithms......Page __sk_0249.djvu
9.1 The Basic Recurrence......Page __sk_0250.djvu
9.2 Wagner-Fischer et al.......Page __sk_0253.djvu
9.3 Hirschberg......Page __sk_0256.djvu
9.4 Hunt-Szymanski......Page __sk_0262.djvu
9.5 Ukkonen-Myers......Page __sk_0268.djvu
9.6 Summary......Page __sk_0275.djvu
10. Approximate Pattern-Matching......Page __sk_0277.djvu
10.1 A General Distance-Based Algorithm......Page __sk_0278.djvu
10.2 An Algorithm for k-Mismatches......Page __sk_0281.djvu
10.3 Algorithms for k-Differences......Page __sk_0286.djvu
10.3.1 Ukkonen\'s Algorithm......Page __sk_0288.djvu
10.3.2 Myers\' Algorithm......Page __sk_0291.djvu
10.4 A Fast and Flexible Algorithm -- Wu and Manber......Page __sk_0298.djvu
10.5 The Complexity of Approximate Pattern-Matching......Page __sk_0304.djvu
11. Regular Expressions and Multiple Patterns......Page __sk_0307.djvu
11.1.1 Non-Deterministic FA......Page __sk_0309.djvu
11.1.2 Deterministic FA......Page __sk_0314.djvu
11.1.3 Algorithm WM Revisited......Page __sk_0317.djvu
11.2.1 Aho-Corasick FA: KMP Revisited......Page __sk_0321.djvu
11.2.2 Commentz-Walter FA: BM Revisited......Page __sk_0325.djvu
11.2.3 Approximate Patterns: WM Revisited Again!......Page __sk_0327.djvu
11.2.4 Approximate Patterns: (Baeza-Yates)-Navarro......Page __sk_0329.djvu
Part IV Computing Generic Patterns......Page __sk_0339.djvu
12. Repetitions (Periodicity)......Page __sk_0341.djvu
12.1.1 Crochemore......Page __sk_0343.djvu
12.1.2 Main and Lorentz......Page __sk_0352.djvu
12.2 Runs......Page __sk_0361.djvu
12.2.1 Leftmost Runs -- Main......Page __sk_0362.djvu
12.2.2 All Runs -- Kolpakov and Kucherov......Page __sk_0368.djvu
13. Extensions of Periodicity......Page __sk_0371.djvu
13.1 All Covers of a String -- Algorithm LS......Page __sk_0372.djvu
13.2 All Repeats -- Algorithm FST......Page __sk_0382.djvu
13.2.1 Computing the NE Tree......Page __sk_0384.djvu
13.2.2 Computing the NE Array......Page __sk_0387.djvu
13.3 k-Approximate Repeats -- Schmidt......Page __sk_0392.djvu
13.4 k-Approximate Periods -- SIPS......Page __sk_0408.djvu
Bibliography......Page __sk_0415.djvu
Index......Page __sk_0427.djvu