L55 · String Algorithms

Series: LeetCode — From Basics to Interview-Ready · Session 55 / 65 · Phase 3 · Advanced & specialised

Why this session exists

KMP is the classic do-you-know-CS question. It has been asked for forty years and it is still asked, partly out of habit and partly because it genuinely separates people who have understood one non-obvious idea from people who have memorised a code snippet.

The non-obvious idea is small: when a match fails partway through a pattern, you already know what the last few characters of the text were — they were the prefix of the pattern you just matched. So you do not need to re-read them. You only need to know how far back to slide the pattern, and that number depends only on the pattern, not the text. Precompute it once and matching becomes a single forward sweep with no backtracking.

That is the whole algorithm. The LPS array is the precomputation. Everything else is index bookkeeping.

I want to be direct about the payoff here. You will probably not need KMP to pass an interview — Python's in operator handles substring search and nobody sensible penalises you for using it. What KMP buys you is the ability to answer "how would you implement that" without freezing, and the ability to solve the periodicity problems (Repeated Substring Pattern, Shortest Palindrome) that are trivial with an LPS array and genuinely hard without one.

Blank-file warm-up

Five minutes, empty file: build the LPS array.

lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i]. "Proper" means it cannot be the whole thing.

The loop is eight lines and contains one while that most people write as an if the first time. If you produce a version where mismatches fall back only one step instead of chaining backwards, that is today's finding — and it is the finding almost everyone gets on their first few attempts.

Sanity target: for "aabaaa" the LPS array is [0, 1, 0, 1, 2, 2]. Check yours against that before moving on.

Pattern anatomy

The shape of problem that summons this: you are searching for, or reasoning about, repeated structure inside a string, and a naive approach would re-examine characters it has already seen.

The invariant KMP maintains during matching: at every step, j characters of the pattern have been matched ending at the current text position, and j is the largest such value possible. On a mismatch, we do not reset j to zero — we reduce it to lps[j-1], which is the largest prefix length still consistent with the text we have consumed. The text pointer i never decreases.

First the LPS build. Note that it is KMP matching the pattern against itself:

def build_lps(p):
    lps = [0] * len(p)
    length = 0                     # length of the current longest prefix-suffix
    i = 1
    while i < len(p):
        if p[i] == p[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]   # WHILE-style fallback, chains backwards
        else:
            lps[i] = 0
            i += 1
    return lps

The elif length: branch is the algorithm. It does not advance i. It shrinks length to the next-best candidate and retries the same position, possibly several times. Writing length = 0 there instead is the classic wrong version — it is fast, it is simple, and it silently produces wrong LPS values on strings like "aabaaab".

Then the search, which is the same loop with two strings:

def kmp_search(text, pat):
    if not pat:
        return 0
    lps = build_lps(pat)
    j = 0
    for i, ch in enumerate(text):
        while j and ch != pat[j]:
            j = lps[j - 1]         # slide the pattern, keep i fixed
        if ch == pat[j]:
            j += 1
        if j == len(pat):
            return i - j + 1       # first match start index
    return -1

i only ever moves forward, once per character. That is why the whole thing is O(n + m).

The rolling hash — Rabin-Karp — attacks the same problem differently. Hash the pattern once, then slide a fixed-width window over the text updating the hash in O(1) per step:

def rabin_karp(text, pat, base=257, mod=(1 << 61) - 1):
    n, m = len(text), len(pat)
    if m > n:
        return -1
    high = pow(base, m - 1, mod)
    hp = ht = 0
    for i in range(m):
        hp = (hp * base + ord(pat[i])) % mod
        ht = (ht * base + ord(text[i])) % mod
    for i in range(n - m + 1):
        if hp == ht and text[i:i + m] == pat:   # verify: hashes can collide
            return i
        if i + m < n:
            ht = ((ht - ord(text[i]) * high) * base + ord(text[i + m])) % mod
    return -1

The verification step is not optional. A hash match is evidence, not proof. Skipping the comparison gives you an algorithm that is usually right, which is the worst kind of algorithm.

And the Z-function, which is often the easiest of the three to write correctly. z[i] is the length of the longest substring starting at i that is also a prefix of the whole string:

def z_function(s):
    n = len(s)
    z = [0] * n
    l = r = 0                      # [l, r) is the rightmost known prefix-match window
    for i in range(1, n):
        if i < r:
            z[i] = min(r - i, z[i - l])
        while i + z[i] < n and s[z[i]] == s[i + z[i]]:
            z[i] += 1
        if i + z[i] > r:
            l, r = i, i + z[i]
    return z

For pattern matching, run it on pattern + sentinel + text and look for positions where z[i] equals the pattern length. The sentinel must be a character absent from both strings.

The cue

You are in string-algorithm territory when:

1. "Implement substring search" or "do not use built-in string find". Explicit invitation. KMP.
2. The problem is about periodicity — "does this string consist of a repeated substring", "what is the smallest repeating unit". The LPS array answers this directly: if n % (n - lps[n-1]) == 0 and lps[n-1] > 0, the string is periodic with period n - lps[n-1].
3. "Longest prefix that is also a suffix" in any phrasing — including the disguised version, "add the fewest characters to the front to make it a palindrome". That last one is Shortest Palindrome, and it is an LPS computation on s + '#' + reverse(s).
4. You need to compare many substrings for equality, cheaply. Rolling hash. Any problem where the inner operation is "are these two substrings the same" and it happens O(n²) times.
5. Naive matching would be O(n·m) and the constraints make that too slow — a pattern of length 10⁴ inside a text of length 10⁵.

Tell 2 is the highest-value one, because the connection between LPS and periodicity is genuinely non-obvious and instantly solves two otherwise-annoying problems.

Guided solve

Implement strStr — return the index of the first occurrence of needle in haystack, or −1.

Say the obvious thing first: haystack.find(needle) solves this and, in real code, is what you should write. The interview is asking for the implementation underneath, so we do KMP. Naming the built-in and then setting it aside costs five seconds and shows judgement.

The naive approach: for each of the n - m + 1 starting positions, compare up to m characters. O(n·m). The pathological input is haystack = "aaaa...a" (length 10⁵) and needle = "aaa...ab" (length 10⁴) — every start position matches almost the entire needle before failing on the last character. A billion comparisons.

The insight that fixes it: when we fail at needle position j, we know the previous j characters of the haystack were exactly needle[0..j-1]. Restarting from start + 1 throws that knowledge away. The most we can preserve is the longest proper prefix of needle[0..j-1] that is also a suffix of it — precisely lps[j-1].

So: build the LPS array, then sweep.

def strStr(haystack, needle):
    if not needle:
        return 0
    m, n = len(needle), len(haystack)
    if m > n:
        return -1
 
    lps = [0] * m
    length, i = 0, 1
    while i < m:
        if needle[i] == needle[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
 
    j = 0
    for i, ch in enumerate(haystack):
        while j and ch != needle[j]:
            j = lps[j - 1]
        if ch == needle[j]:
            j += 1
            if j == m:
                return i - m + 1
    return -1

Trace the fallback once with needle = "aab", haystack = "aaab". LPS is [0, 1, 0]. At haystack index 2 we have j = 2 and see 'a' where the needle wants 'b'. Rather than restarting, j falls to lps[1] = 1 — we still have one matched 'a'. Now 'a' == needle[1], so j becomes 2. At index 3, 'b' == needle[2], j reaches 3, match found at index 1. The text pointer never moved backwards.

That trace is what you should narrate in an interview. The code is unremarkable; the trace is the demonstration.

Solo timed

Fifteen minutes each.

• Repeated Substring Pattern — the answer is one line once you have the LPS array. Think about what n - lps[n-1] represents when the string is built from a repeated block.
• Shortest Palindrome — you are looking for the longest palindromic prefix. Build a combined string from s, a separator that appears in neither half, and reverse(s), then read off the last LPS value.

Common failure modes

Using if instead of while in the LPS fallback. The fallback must chain: after length = lps[length-1], the characters may still not match, so you retry. A single-step fallback produces a subtly wrong LPS array that still passes short test cases. "aabaaab" exposes it.

Advancing i in the fallback branch. The fallback re-examines the same pattern position with a smaller candidate length. If you advance i there, you skip a position and the array is short by one entry in exactly the interesting cases.

Skipping verification after a rolling-hash match. Hash collisions happen. With a 64-bit modulus they are rare, and rare is not never — and LeetCode's test suites for hash problems sometimes include a crafted collision. Always compare the actual substring.

Forgetting the sentinel in the Z-function approach. Running the Z-function on pattern + text without a separator lets matches straddle the boundary, and you get false positives whose position arithmetic looks plausible. The separator must be a character absent from both strings.

Reading lps[j] instead of lps[j-1] on mismatch. The mismatch happened at position j, so the matched region ends at j-1, and it is that region's prefix-suffix length you want. This is an off-by-one that produces an infinite loop rather than a wrong answer, so at least it is loud.

Empty-needle handling. By convention strStr("", "") returns 0 and any empty needle returns 0. Handle it in the first line.

Complexity

LPS build: O(m). It looks quadratic because of the inner while, but length increases at most once per iteration of the outer loop and never goes below zero, so the total number of decreases is bounded by the total number of increases — at most m. Amortised linear. Space O(m).

KMP search: O(n) after the build, same amortised argument on j. Total O(n + m) time, O(m) space.

Rabin-Karp: O(n + m) expected. Worst case O(n·m) if every window collides and forces verification. Space O(1).

Z-function: O(n), because the r boundary only moves right and the inner while only runs when it does. Space O(n).

Spaced queue

Re-solve what is due before new material. Status ladder:

• cold — clean, unaided → 60 days
• warm — solved with a stumble → 21 days
• hint — needed a nudge → 7 days
• failed — no working solution → 2 days, then 7 days

The LPS build should sit in your queue permanently at a short interval until you produce it correctly three times running. It decays faster than almost anything else in this track, because it is pure index arithmetic with no intuitive anchor.