Command Palette

Search for a command to run...

Hectal

Module 35

Advanced String Algorithms

Linear-time pattern matching with KMP and the Z-function, rolling hashes for comparing many substrings, and where Manacher fits.

Advanced 3 lessons 7 problems ~45 min of lessons
String Matching (KMP, Z, Rolling Hash)

Searching for a pattern of length m in a text of length n by trying every start costs O(n × m) in the worst case. The algorithms in this module avoid re-reading characters: KMP and the Z-function remember how much of the pattern already matched, and rolling hashes compare whole substrings by number in O(1).

You'll build the KMP failure table step by step, compute Z-arrays, use Rabin-Karp hashing with collision checks, and apply them to classic problems: first occurrence, repeated patterns, shortest palindromes, happy prefixes, repeated DNA and the longest duplicated substring.

Best after: Strings, Hashing

Where this shows up in real systems

Part 1

Learn the ideas

  1. 35.1KMP: Never Re-Read the TextThe failure table lps[i] stores the longest proper prefix of the pattern that is also a suffix of pattern[0..i]. On a mismatch, jump back to that prefix instead of restarting.18 min
  2. 35.2The Z-Functionz[i] is the length of the longest substring starting at i that matches a prefix of the string. Searching for p in t becomes computing Z of p + '$' + t.12 min
  3. 35.3Rolling Hashes (Rabin-Karp)Treat a substring as a number in base B modulo a large prime. Sliding the window by one updates the hash in O(1), so all substrings of a length can be compared quickly.14 min

Part 2

Solve the problems

Work through them in order. Each one shows the pattern it teaches.

  1. 35.1Find the Index of the First Occurrence in a StringEasyString Matching (KMP, Z, Rolling Hash)

    KMP end to end: build lps, then scan the text once.

  2. 35.2Repeated Substring PatternEasyString Matching (KMP, Z, Rolling Hash)

    The lps of the whole string reveals its smallest period.

  3. 35.3Rotate StringEasyString Matching (KMP, Z, Rolling Hash)

    Every rotation of s is a substring of s + s.

  4. 35.4Longest Happy PrefixHardString Matching (KMP, Z, Rolling Hash)

    The answer is exactly lps[n − 1].

  5. 35.5Shortest PalindromeHardString Matching (KMP, Z, Rolling Hash)

    KMP on s + '#' + reverse(s) finds the longest palindromic prefix in O(n).

  6. 35.6Repeated DNA SequencesMediumString Matching (KMP, Z, Rolling Hash)

    A rolling 2-bit-per-letter code makes each 10-letter window a 20-bit integer.

  7. 35.7Longest Duplicate SubstringHardString Matching (KMP, Z, Rolling Hash)

    Binary search on the length, with a rolling-hash check for each length.