Strings

Finding a word inside a text sounds easy until the text is a book or a genome. These algorithms avoid re-reading letters by remembering what each comparison already proved. Each one has a live visualizer running the real code.

1. 01KMP searchFind a pattern without ever stepping back in the text, using a table of the pattern’s own repeats.O(n + m)
2. 02Z-functionFor every position, how long a stretch matches the start of the string.O(n)
3. 03Rabin-KarpCompare rolling hashes of each window, and only check letters when the hashes match.O(n + m) avg
4. 04Suffix arraySort every suffix of a word, so any substring search becomes a binary search.O(n³) naive