AlgoScope

String Algorithms

Finding one pattern, many patterns, or every repeat inside a text, without re-reading characters you have already compared.

13 topics4 lessons2 families

Searching a text of length n for a pattern of length m the obvious way tries each of the n - m + 1 alignments and compares up to m characters at every one. That is O(n * m) in the worst case, and the waste is specific: a mismatch after eight matching characters throws away the fact that those eight characters are known.

Each algorithm here keeps a different part of that knowledge. The prefix function records, for every prefix of the pattern, the longest proper prefix that is also a suffix; KMP uses it to slide the pattern forward without ever moving the text pointer back, O(n + m). The Z algorithm stores the same information as match lengths starting at each position. Boyer-Moore compares from the right and, on a character that does not occur in the pattern at all, jumps a whole pattern width. Rabin-Karp keeps no character knowledge at all, only a rolling hash of the current window, and reads characters only when two hashes agree.

Past a single pattern the structures change. A trie stores a set of strings by shared prefix, so a lookup costs the length of the word and nothing per stored word; add failure links to it and it becomes Aho-Corasick, which reports every occurrence of every pattern in one pass over the text. A suffix array sorts all n suffixes, in O(n log n) by doubling the compared prefix each round, and turns repeats and substring counts into binary searches. Manacher handles palindromes in O(n) by copying radii from the mirror inside the palindrome it is already in.

After this you can

  • Build a prefix function by hand and step through KMP with it
  • Say what each algorithm keeps from a mismatch and what it throws away
  • Choose between a trie, Aho-Corasick and a suffix array by whether the text or the patterns are fixed
  • Explain why Rabin-Karp has to verify a hit and what the cost becomes when hits are frequent
  • Recognise the palindrome questions that Manacher answers in linear time
txtpata✓b✓c✓a✓b✓c×abda✓b✓c✓a✓b✓d×c > d

Shift 0: pattern under "abcabc". 5 agree, then 'c' differs from 'd'. Move on to shift 1.

Open in the player →or start at step 2

In this order

  1. Naive Pattern MatchingTry every alignment and compare left to right, throwing away what was read at each mismatch.
  2. Rabin-KarpCompare a rolling hash of each window with the pattern hash and read characters only on a hash hit.
  3. Prefix FunctionFor each prefix, the length of its longest proper prefix that is also a suffix, built by falling back through shorter borders.
  4. Knuth-Morris-PrattOn a mismatch, drop j to pi[j - 1] so the pattern slides without re-reading any text character.
  5. Z Algorithmz[i] is the longest prefix match starting at i; inside the rightmost match box copy from the mirror, then extend.
  6. Boyer-MooreCompare from the right; on a mismatch slide so the pattern's last copy of the bad character lines up, or past it.
  7. ManacherLongest palindromic substring in O(n) by reusing mirrored palindrome radii.
  8. Trie InsertWalk existing character edges, create the missing ones, and mark the final node terminal.
  9. Trie SearchWalk the characters; the word exists if the walk succeeds and ends on a terminal node.
  10. Trie DeleteUnmark the terminal; prune nodes upward while they have no children and are not terminal.
  11. Prefix Search and AutocompleteWalk the prefix, then enumerate every terminal below it with a DFS.
  12. Aho-CorasickA trie of all patterns plus failure links; matches many patterns in one pass over the text.
  13. Suffix Array ConstructionSort suffixes by doubling the compared prefix length each round.

Where people go wrong

Trusting a hash match in Rabin-Karp

Equal hashes do not mean equal strings. Compare the characters on every hit; skipping that check is what turns a linear algorithm into a wrong one, and a weak or small modulus lets an adversarial text force a verification at every position, back to O(n * m).

The wrong index in the prefix-function fallback

pi[i] is the border length of the prefix ending at i, and a length is also the index of the next character to compare. On a mismatch at position j you fall back to pi[j - 1], never pi[j]; getting that one off by one wrong either loops forever or silently skips matches.

Assuming one character is one byte

Indexing bytes works for ASCII and breaks on everything else, because a single character can be several bytes and reversing or comparing at byte level produces invalid text. Decide early whether the alphabet is bytes, code points or something else, and size the shift tables to match.

Or a different category

Hashing

You look up whole strings by exact value rather than searching inside one, and a hash map answers in a single step.

Sliding Window

The question is about a stretch of text defined by a condition, such as the longest run with no repeated character, rather than about matching a fixed pattern.

Lessons that teach these