String Algorithms

Review boundary and corrected contracts

KMP fallback follows borders without rescanning consumed text. Rabin–Karp handles empty patterns before computing powers and confirms every hash hit with exact comparison. Fixed base/modulus has no unconditional expected-time promise; adversarial collisions give O(nm), with O(m) Python slice storage.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Build the LPS array from a blank file and understand why it lets KMP never move the text pointer backwards. Then know rolling hash and the Z-function as alternatives with different failure modes.

Series: LeetCode — From Basics to Production-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 design review — 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 detail to reconstruct is the retry: a mismatch may require several shorter border candidates before the current character can be classified. The implementation below retries through its outer while, leaving i unchanged on fallback. A version that advances after only one failed fallback loses that invariant.

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.

Before processing text index i, j is the length of the longest pattern prefix matching a suffix of text[:i]. On a mismatch with text[i], follow lps[j-1] to the next possible border and retry the same character. After a match, increment j; a full pattern ends the search. The text index never decreases, but one text character can participate in several comparisons during fallback.

To see what that fallback preserves, imagine that the matched pattern prefix is abab and the next text character fails to extend the match. The suffix ab is already a prefix of the pattern, so those two matched characters can survive the failure; there is no reason to compare them with the text again. LPS records the longest proper prefix that is also a suffix at each pattern position. If that shorter candidate also fails, its own LPS entry supplies the next candidate. First build those links by 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 advances once per consumed text character, and each successful extension increases j by at most one. Each fallback strictly decreases j; total decreases cannot exceed total increases. This amortised argument, not monotonic i alone, proves O(n) matching after O(m) preprocessing.

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 == 0:
        return 0
    if mod <= 1:
        raise ValueError("modulus must exceed one")
    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". For nonempty strings 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 + separator + reverse(s), with a separator absent from s ('#' suffices for lowercase letters).
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 design review 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 under a tight review. 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

Failing to retry after a fallback. build_lps uses an outer while plus an elif, not a literal inner while: it is correct because the fallback branch leaves i unchanged. The error is permitting only one fallback before consuming the character. Replacing its fallback assignment with length = 0 fails on "aabaaab", whose correct LPS is [0, 1, 0, 1, 2, 2, 3].

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 some preallocated entries remain incorrectly zero because their positions were never classified.

Skipping verification after a rolling-hash match. Fixed base and modulus do not guarantee a collision probability for arbitrary inputs. Even a large modulus is not a proof. With base 1 and modulus 2, "ac" and "bb" collide but differ; exact comparison must reject that candidate. The displayed verified search is deterministic in its answer, although collisions can worsen its time.

Changing the Z matching contract. With an absent separator in pat + separator + text, Z values at text positions cannot exceed len(pat), so equality detects matches. Without the separator, the method can still work if you scan only text-start positions and test z[i] >= len(pat). Keeping the equality test can miss a match: pat="aa", text="aaa" gives combined "aaaaa" and z[2]=3, not 2. The separator simplifies the proof; omitting it does not inherently create false positives at correctly selected text positions.

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.

Myth: KMP is fast because it skips ahead in the text, jumping over characters it knows cannot match.

Why: KMP consumes text positions in order until it finds the first match or exhausts the text. It may compare the current character against several pattern positions while following failure links, but it never rewinds to a consumed text position. Boyer–Moore uses a different idea: right-to-left pattern comparison and shifts that can skip candidate alignments.

Steps 1: Naive matching restarts comparison at the next text index after every failure, discarding everything it learned from the partial match.

Steps 2: Because a partial match of length j means the last j text characters are exactly pattern[0..j-1], those characters are already known and need not be re-read.

Steps 3: Because they are known, the only question is how far the pattern can slide while still aligning with them — and that depends only on the pattern's own structure.

Steps 4: Because it depends only on the pattern, it can be precomputed once: for each j, the longest proper prefix of pattern[0..j-1] that is also a suffix of it.

Steps 5: A mismatch can require several failure-link lookups before the current character is consumed. Each lookup strictly reduces the matched-prefix length, which can increase at most once per consumed character. That potential argument bounds all fallback work together.

Steps 6: KMP takes O(n + m) total work. On an all-a text and a long a…ab pattern, naive search repeatedly compares nearly m characters per alignment while KMP amortises fallback across the scan. The asymptotic contrast does not specify an elapsed time.

Picture: A physical ruler with the pattern printed on it, laid over the text. When the alignment breaks, you do not lift the ruler and start again at the next character — you slide it right just far enough that its printed prefix lands on the matching suffix you already verified. The LPS array is the table telling you how far to slide.

Trigger: Fires whenever a matching or scanning process is about to re-examine input it has already consumed.

Name: KMP

Gain: Deterministic O(n + m) with no failure probability; the LPS array is reusable and directly answers periodicity questions

Cost: The build loop is the most error-prone twenty lines in the review canon; needs a full rewrite for multi-pattern search

Name: Rolling hash (Rabin-Karp)

Gain: Prefix hashes can provide O(1) candidate substring-hash comparisons after O(n) preprocessing under fixed-width arithmetic. Multiple patterns can be grouped by length and hash; 2D matching needs a separate two-dimensional construction, not the unchanged single-pattern code.

Cost: Unverified hash equality can be wrong; the displayed exact verification removes answer error but can cost O(m) per candidate and O(n·m) overall. Fixed parameters alone give no unconditional expected-time guarantee.

Pick: KMP when you need a single-pattern search with a hard worst-case guarantee, or when the question is really about periodicity. Rolling hash the moment you need to compare many arbitrary substring pairs, search for several patterns at once, or you are under time pressure and cannot risk the LPS build coming out wrong.

Complexity

LPS build: O(m). An iteration either advances i, or keeps i fixed and strictly decreases length. There are at most m advances, and length can increase only when an advance matches a character. Since it starts at zero and stays nonnegative, total fallback decreases cannot outnumber total increases. Thus the repeated retries are amortised linear even without a literal nested loop. 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) when spurious hash matches are sufficiently rare; fixed parameters alone do not establish an expectation. Worst case O(n·m) if every window collides and forces verification. The hash state is O(1); the Python verification slice can allocate O(m).

Z-function: O(n) time and O(n) space. If a reused Z value ends strictly inside the known window, the next comparison fails immediately; it costs at most one such failure per position. Otherwise successful new comparisons extend the right boundary, which advances at most n times. A failed loop-condition comparison can occur inside an old window; the proof counts those failures as well as successful extensions beyond the known boundary.

Self-check (answer follows each question).

Q: Define lps[i] precisely.

A: The length of the longest proper prefix of pattern[0..i] that is also a suffix of pattern[0..i]. 'Proper' excludes the whole substring itself, which is why lps[0] is always 0.

Q: Why must LPS fallback retry the same character until a border matches or the candidate length becomes zero?

A: A shorter border can still mismatch. The displayed outer while retries because its fallback branch does not advance i; an inner while is an equivalent arrangement. Resetting to zero rather than following borders fails on aabaaab. The requirement is repeated fallback, not a particular choice of if versus while syntax.

Q: Given the LPS array of a string of length n, how do you test whether the string is a repetition of a smaller block?

A: For a nonempty string, let p = n − lps[n−1]. It is a repetition of a smaller block exactly when lps[n−1] > 0 and n % p == 0. Without divisibility, p is still the shortest period in the overlap sense, but not a whole-number repetition. Handle an empty input separately.

Q: Why does the LPS build run in O(m) despite potentially repeated fallbacks at one position?

A: At most m iterations advance i. Matching advances can increase length by one; fallback iterations strictly decrease it without advancing i. Its total decreases are bounded by its total increases, so those extra iterations are O(m) as well. This accounts for all iterations of the displayed outer loop.

Q: Why is verification mandatory after a rolling-hash match?

A: Equal hashes do not imply equal strings — collisions exist and can be adversarially constructed. The hash narrows candidates; the direct comparison confirms them.

Q: How would you turn KMP into a search for many patterns at once, and what is that structure called?

A: Build a trie with failure links: Aho–Corasick. With a fixed alphabet and constant-time transition handling, construction and scanning take O(total pattern length + n + reported matches). Alphabet representation and output reporting are part of that bound; no automaton implementation is supplied here.

Stretch: true

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.

• KMP's idea in one sentence: a partial match tells you what the recent text was, so never re-read it — slide the pattern instead.

• The text pointer never moves backwards. KMP does not skip characters, it avoids revisiting them.

• The LPS fallback must retry the current character, via the shown outer loop or an inner while, and use lps[j-1], not lps[j].

• For nonempty s, n − lps[n−1] yields the candidate repetition length; check divisibility. Shortest Palindrome instead uses the final LPS of s + separator + reverse(s) to measure the longest palindromic prefix.

• Prefix hashes give O(1) candidate hash comparisons under bounded-word arithmetic, not O(1) verified substring equality. Exact comparison after a hash hit removes answer error at an O(m) worst-case verification cost.

• The Z-function is usually the easiest of the three to write correctly; with a sentinel it does pattern matching too.

Corrective source notes

• Prefix function - Knuth-Morris-Pratt - Algorithms for Competitive Programming — The prefix function is the longest proper prefix that is also a suffix of each prefix ending at i. Checked 2026-10-07.
• Z-function - Algorithms for Competitive Programming — A Z value measures the longest prefix match beginning at the indexed position. Checked 2026-10-07.
• String Hashing - Algorithms for Competitive Programming — Equal hashes are not sufficient to establish equal strings. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.