| WORLD SCIENTIFIC'S LECTURE NOTES SERIES ON COMPUTING | ||||
|
STRING SEARCHING ALGORITHMS by Graham A Stephen |
||||
|
1 Introduction 2 String Matching Overview Brute Force Knuth-Morris-Pratt and Boyer-Moore Approaches Hashing Functions Comparative Performance Popularity Multiple-String Searches Algorithms in Detail Brute Force Knuth-Morris-Pratt Boyer-Moore Boyer-Moore-Horspool Sunday -- Quick Search, Maximal Shift, and Optimal Mismatch Hume and Sunday -- Tuned Boyer-Moore and Least Cost Harrison Karp-Rabin Further Reading 3 String Distance and Common Sequences Overview String Distance Measures String Distance and Longest Common Subsequence Comparative Performance Related Problems Algorithms in Detail Wagner-Fischer Hirschberg Hunt-Szymanski Masek-Paterson Ukkonen Heaviest Common Subsequence Further Reading |
|
4 Suffix Trees Overview Suffix Tries From Suffix Trie to Suffix Tree Algorithms in Detail Brute Force McCreight Ukkonen Further Reading 5 Approximate String Matching Overview String Matching with k Mismatches String Matching with k Differences String Matching with Don't-Cares Application Areas Dedicated Hardware and Parallel Algorithms Algorithms in Detail Landau-Vishkin k-mismatches Shift-Add Tarhio-Ukkonen k-mismatches Baeza-Yates--Perleberg k-mismatches Dynamic Programming k-differences Landau-Vishkin k-differences Chang-Lawler k-differences Chang-Lampe k-differences Wu-Manber k-differences Further Reading 6 Repeated Substrings Overview Repetitions Longest Repeated Substrings Algorithms in Detail Brute Force Suffix Trees A Asymptotic Notation B String Symbology C Glossary D Bibliography |
||
| ||||