← Algorithm Design learning pathAlgorithm Design · Module 7 of 10
String algorithms
Search and process text efficiently.
📖 Key ideas
- Naive pattern search is O(nm).
- KMP uses a prefix table for O(n + m) search.
- Rabin-Karp uses rolling hashes.
- Tries store strings for fast prefix lookups.
- Applications: search engines, DNA analysis, autocomplete.
💡 Real-life example: KMP is a reader who remembers what already matched, so never rereads the same letters.
Pattern matchingFinding a pattern in text
KMPKnuth-Morris-Pratt algorithm
Rolling hashHash updated as window slides
TriePrefix tree for strings