Part VIII · String Algorithms and Text Indexing
48. String Pattern Matching Algorithms
7 lessons•34 topics•Advanced / Expert
0 of 7 lessons published
48.01Outline
Naive pattern matching
- Sliding compare
- Worst-case behavior
- Empty pattern
- Overlap handling
48.02Outline
Prefix-function KMP
- Borders
- Prefix function pi
- Build prefix array
- KMP search
- Border enumeration
48.03Outline
Z algorithm
- Z array
- Z-box invariant
- Pattern search
- Prefix match lengths
- String period detection
48.04Outline
Rabin-Karp
- Rolling hash
- Polynomial hash
- Prefix hash
- Double hashing
- Collision handling
- Substring equality
48.05Outline
Finite automata matching
- DFA states
- Transition table
- Pattern automaton
- Complexity trade-offs
48.06Outline
Boyer-Moore family
- Bad-character rule
- Good-suffix rule
- Horspool
- Sunday algorithm
- Practical string search
48.07Outline
Multiple-pattern matching
- Trie-based search
- Aho-Corasick
- Failure links
- Output links
- Dictionary matching