String matching

Problem

The question is always some form of "where does this string occur inside that one?", sometimes disguised: does a string repeat a smaller block, what is the longest prefix that is also a suffix, which substrings appear twice, or how few characters must be added to make a palindrome. A direct comparison at every start costs O(nm) when the text and pattern are full of near-matches, like long runs of one letter. The fix is to reuse what earlier comparisons already proved, either through the pattern's own structure (KMP) or through arithmetic on the window (rolling hash).

Intuition

Slide the pattern abcabd along the text abcabcabd. At start 0, the first 5 characters match and then position 5 fails. The naive method shifts by one and starts over, re-reading characters it has already seen. But the 5 characters that matched are now known: they are abcab. That text ends in ab, which is also how the pattern begins. So the pattern can jump straight to start 3, with its first 2 characters already matched, and carry on from the same text position.

The amount to keep depends only on the pattern, never on the text, so it can be computed once: for every prefix of the pattern, the longest piece that is both a proper prefix and a suffix of it. That piece is called a border, and the list of border lengths is the failure table.

Rabin–Karp takes a different route. Turn each window of m characters into a number, the way digits make a number, and keep it small with a modulus. Sliding the window one step removes the leading digit and appends a new one, in O(1). Equal strings always have equal hashes, so only windows whose hash equals the pattern's need a real comparison.

Green cells match the text and the red outline is the mismatch. On the second row, amber is the border carried over without being compared again; the text pointer stays at 5. The diagram scrolls sideways on a narrow screen.

Mechanics

The failure table

lps[i] is the length of the longest proper prefix of pattern[:i + 1] that is also its suffix. Build it left to right with a pointer length holding the current border. If the next character extends the border, it grows by one. If not, the next-longest border to try is the border of the border, lps[length − 1], because any border of a string that is shorter than its longest border must also be a border of that longest border. Keep falling back until the character extends one or the length reaches 0.

The search

Keep j, the number of pattern characters matched so far, and read the text once. On a match, j grows. On a mismatch with j > 0, set j = lps[j − 1] and try the same text character again. The invariant: pattern[:j] equals the j text characters just before i, and no occurrence starts at an earlier position not yet ruled out. The fallback keeps it, because the longest border is the largest shift-back that still agrees with the text, and every start in between would contradict the matched characters. When j reaches m, record a match at i − m + 1 and fall back once more so overlapping matches are found.

Why it is linear

Each text character raises j by at most 1, and each fallback lowers it by at least 1. j never goes below 0, so the total number of fallbacks over the whole search is at most n, and the search does at most 2n comparisons. The same argument bounds the table build by 2m.

The rolling hash

Give each letter a value (here a = 1, b = 2, and so on) and read a window as a number in base B, modulo a prime p. Moving the window right one place subtracts the leaving letter times B^m−1, multiplies by B and adds the arriving letter, all mod p. Equal windows always hash equal, so no match is missed; unequal windows can collide, so a hash hit must be confirmed by comparing characters. With a large random prime, collisions are rare and the expected time is O(n + m).

Worked example

Failure table for abcabd.

KMP over abcabcabd. One row per text character:

KMP makes 10 character comparisons and the naive method 14, both finding the match at 3. After a match, j falls back to lps[m − 1] instead of 0, which is what lets overlapping matches be found.

Rabin–Karp: abd in bcabdadcab, base 26, modulus 11. The pattern hashes to 6, and B^m−1 mod 11 = 5:

The match is at 2; the window at 4 collides. A modulus as small as 11 makes collisions easy to show. Real code uses a prime near 2⁶¹, where a collision is about as likely as winning a lottery.

Only the two windows whose hash is 6 are compared letter by letter. The green box is a match; the red one is a collision.

Implementation

def build_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    for i in range(1, len(pattern)):
        while length and pattern[i] != pattern[length]:
            length = lps[length - 1]
        if pattern[i] == pattern[length]:
            length += 1
        lps[i] = length
    return lps


def kmp_search(text, pattern):
    if not pattern:
        return [0]
    lps = build_lps(pattern)
    matches, j = [], 0
    for i, ch in enumerate(text):
        while j and ch != pattern[j]:
            j = lps[j - 1]
        if ch == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - j + 1)
            j = lps[j - 1]
    return matches

Variations and edge cases

Rabin–Karp. With a modulus near 2⁶¹, Python's big integers keep the arithmetic exact, and the slice comparison makes a collision harmless:

def rabin_karp(text, pattern, base=131, mod=(1 << 61) - 1):
    m = len(pattern)
    if m > len(text):
        return []
    high = pow(base, m - 1, mod)
    target = window = 0
    for k in range(m):
        target = (target * base + ord(pattern[k])) % mod
        window = (window * base + ord(text[k])) % mod
    matches = []
    for start in range(len(text) - m + 1):
        if start:
            window = ((window - ord(text[start - 1]) * high) * base + ord(text[start + m - 1])) % mod
        if window == target and text[start:start + m] == pattern:
            matches.append(start)
    return matches

The Z-array. z[i] is the length of the longest substring starting at i that matches a prefix of the string. A window [left, right) remembers the furthest match so far, and positions inside it start from a value already known. Searching is then z_array(pattern + "#" + text) and reporting every i where z[i] == len(pattern), with "#" any character in neither string:

def z_array(s):
    z = [0] * len(s)
    left = right = 0
    for i in range(1, len(s)):
        if i < right:
            z[i] = min(right - i, z[i - left])
        while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > right:
            left, right = i, i + z[i]
    return z

Analysing the pattern itself. build_lps(s)[-1] is the longest border of s. If the border is non-zero and p = n − border divides n, s is a block of length p repeated. And running the table over s + "#" + reversed(s) gives the longest palindromic prefix of s.

• Empty pattern. By convention it occurs at 0; pattern[j] with an empty pattern would raise, so return early.
• Overlapping matches. Resetting j to 0 after a match misses aa at 1 in aaa; fall back to lps[m − 1].
• Negative modulo. Subtracting the leaving letter can go negative. Python's % always returns a non-negative result, but in languages where it does not, add the modulus back.
• Trusting a hash hit. Skipping the character check turns a collision into a wrong answer. Either compare, or use two independent hashes and accept a tiny risk knowingly.

Complexity and tradeoffs

KMP is O(n + m) time in the worst case and O(m) extra space. Rabin–Karp is O(n + m) expected, O(nm) if every window collides, and O(1) extra space. The Z-array is O(n + m) time and space. The naive method is O(nm) in the worst case, reached when the text is all one letter and the pattern differs only at its end:

• KMP or Rabin–Karp. KMP has a guarantee and needs no luck. Rabin–Karp generalises: hash every length-L window of one or many strings and compare them through a set, which KMP cannot do.
• Against the built-in. CPython's str.find and in are written in C and are fast on ordinary text. Reach for these patterns when the problem is about the pattern's structure, or when you need all windows' hashes.
• Against a trie. Matching many patterns at once is the job of a trie (and the Aho–Corasick automaton, which adds failure links like KMP's to a trie).
• Against suffix structures. Suffix arrays and suffix automata answer many queries over one fixed text, at a cost no interview expects you to write.

Problems

No problem on the four lists has this page as its home, which is why it sits under Beyond the interview.

For practice beyond the lists, in rising difficulty:

• 28. Find the Index of the First Occurrence in a String Easy
  The search on this page, stopping at the first match.
• 459. Repeated Substring Pattern Easy
  The last failure-table entry gives the longest border; the string repeats exactly when that border is non-zero and n minus it divides n.
• 187. Repeated DNA Sequences Medium
  Every window has the same short length, so roll a hash (or a bit-packed code) and keep a set of those seen.
• 1392. Longest Happy Prefix Hard
  This is the failure table's last entry, nothing more.
• 214. Shortest Palindrome Hard
  The longest palindromic prefix is the longest border of the string glued to its reverse with a separator.
• 1044. Longest Duplicate Substring Hard
  Binary search the length and test each with a set of rolling hashes, confirming hits.

Connections

Rabin–Karp is a hash set over windows, rolled the way a fixed-size window rolls a sum. KMP's failure table is a small DP over prefixes, each entry built from earlier ones, and its matching loop is a finite automaton; adding the same failure links to a trie matches many patterns at once. Hashing also turns "longest repeated substring" into a binary search on the answer, and the palindrome tricks here sit next to the palindrome DP page.

Check yourself

References

• Knuth, D. E., Morris, J. H. and Pratt, V. R., "Fast pattern matching in strings", SIAM Journal on Computing 6(2):323–350, 1977.
• Karp, R. M. and Rabin, M. O., "Efficient randomized pattern-matching algorithms", IBM Journal of Research and Development 31(2):249–260, 1987.
• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 3rd edition, chapter 32, "String Matching" (32.2 Rabin–Karp, 32.4 Knuth–Morris–Pratt).
• Sedgewick and Wayne, Algorithms, 4th edition, section 5.3, "Substring Search".
• Skiena, S., The Algorithm Design Manual, the catalog entry "String Matching".
• Gusfield, D., Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997, chapter 1, for the Z-algorithm.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.