String Matching Interview Questions: KMP Prefix Tables and Overlapping Matches

String matching interview questions become difficult when the interviewer moves past “find the first occurrence.” A correct answer must state the matching contract, build a prefix table without guessing, preserve overlapping matches, and defend the complexity on repetitive input. Knuth-Morris-Pratt (KMP) solves exact single-pattern search in O(n + m) time with O(m) extra space because a mismatch reuses information already proved about the pattern instead of moving the text pointer backward.

Use Implement string matching with follow-up for the basic first-occurrence exercise. This guide develops the follow-ups that expose whether you understand KMP: tracing a border chain, reporting every overlap, and recognizing when rolling hash or a multi-pattern automaton fits the contract better. PracHub question records are candidate-reported practice material, not predictions of a particular employer’s interview.

String Matching Interview Questions: Quick Answer

Say that pi[i] is the length of the longest proper prefix of the pattern that is also a suffix of pattern[0:i+1]. During the scan, q is the number of pattern characters currently matched. If text[i] != pattern[q], replace q with pi[q - 1] until the new border can accept the character or q becomes zero. The text index never moves backward.

After a complete match, report i - m + 1 and set q = pi[m - 1]. That final fallback is what preserves overlaps. For text = "aaaaa" and pattern = "aaa", resetting q to zero finds only the first occurrence; falling back to two finds starts 0, 1, and 2.

The original Knuth-Morris-Pratt paper describes a matcher whose work is proportional to the combined lengths of the pattern and text without backing up the input. That is an algorithmic guarantee, not evidence that every interview requires KMP.

Treat the prefix table as a chain of reusable borders

A border is a nonempty string that is both a prefix and a suffix, but not the whole string. The prefix table stores the longest border length for every pattern prefix. Consider pattern = "ababaca":

The interesting entry is i = 5. Before reading c, the current border length is three, representing aba. Comparing pattern[5] with pattern[3] gives c != b, so fall back to pi[2] = 1. Now compare c with pattern[1] = b; that also fails, so fall back to pi[0] = 0. Since c != pattern[0], the new value stays zero.

This trace explains two details candidates often memorize incorrectly. Fallback reads pi[q - 1] because q is a length, while array indexes are zero-based. And it may happen more than once: a border can have its own shorter border. The table is therefore a linked chain encoded in an array, not a collection of independent shift distances.

Build the prefix table without restarting comparisons

The implementation mirrors that definition:

def prefix_table(pattern: str) -> list[int]:
    pi = [0] * len(pattern)
    for i in range(1, len(pattern)):
        q = pi[i - 1]
        while q > 0 and pattern[i] != pattern[q]:
            q = pi[q - 1]
        if pattern[i] == pattern[q]:
            q += 1
        pi[i] = q
    return pi

State the invariant before typing: immediately before assigning pi[i], q is the longest border length still compatible with the comparisons made so far. The while loop tests successively shorter valid borders; it never tests a length that has not already been proved to be a border.

Use three quick checks. A pattern with no repetition such as abcd produces all zeros. aaaa produces [0, 1, 2, 3]. The fallback example ababaca produces [0, 0, 1, 2, 3, 0, 1]. If those disagree, debug the table before combining it with the text scan.

Search without moving the text pointer backward

Once the pattern is preprocessed, the text scan uses the same state transition:

def find_all(text: str, pattern: str) -> list[int]:
    if pattern == "":
        return list(range(len(text) + 1))

    pi = prefix_table(pattern)
    matches = []
    q = 0

    for i, char in enumerate(text):
        while q > 0 and char != pattern[q]:
            q = pi[q - 1]
        if char == pattern[q]:
            q += 1
        if q == len(pattern):
            matches.append(i - len(pattern) + 1)
            q = pi[q - 1]

    return matches

The text character is reconsidered against shorter borders while i stays fixed. That is safe because each fallback preserves a suffix of the text already consumed that is also a prefix of the pattern. Increment i only through the outer loop. A common wrong answer increments the text index inside the mismatch branch, skipping a character that could begin the next match.

The empty-pattern behavior is a contract choice. This version follows the mathematical convention that an empty pattern occurs at every boundary, so a three-character text returns four positions. Many interview APIs instead return 0, [], or reject the input. Any choice can be correct if you state it before coding and test it consistently.

Overlapping matches use the same fallback rule

For text = "aaaaa" and pattern = "aaa", the prefix table is [0, 1, 2]. After characters at indexes 0..2 complete a match, the final two a characters are already a valid prefix for a possible match beginning at index one. Assigning q = pi[2] = 2 preserves that fact. The next text character completes the second match immediately, and the process repeats.

This is the most useful overlap checksum:

The candidate-reported substring match generator makes this output contract explicit. It asks for one yielded result per occurrence and says overlaps count. That record is useful practice evidence; it does not establish how another company will word the task.

Prove the linear bound instead of pointing at two loops

An interviewer may challenge the nested while loop. “The code has two loops” is not a complexity proof. Use a monotonic-accounting argument.

During prefix construction, q increases by at most one for each i, so total increases are at most m - 1. Every fallback strictly decreases q. Across the whole loop, total decreases cannot exceed the accumulated increases. Prefix construction is therefore O(m).

The text scan follows the same reasoning. The outer loop consumes exactly n characters. Successful comparisons increase q, and every failure transition strictly decreases it without rewinding i. The total number of state advances and fallbacks is linear in n; reporting z matches adds O(z) output work. The complete bound is O(n + m + z) for all positions and O(n + m) when only the first match is requested.

This proof is an inference from the state transitions. It is stronger than claiming that KMP is always faster in practice. Library substring search can use specialized algorithms, vector instructions, and short-pattern optimizations. Choose KMP when its worst-case guarantee, streaming scan, or explicit prefix-state behavior answers the interview contract.

Walk through one mismatch before presenting the code

Suppose the pattern is ababaca and the text has already matched ababa. The next text character is a, while the next pattern character is c. Do not say “shift the pattern” and skip to the result. State the facts the algorithm still knows.

The matched text suffix aba equals the pattern prefix aba, so a candidate alignment of length three remains. Comparing the same text character with pattern position three fails because it expects b. The border of aba has length one, so fall back to a. Comparing again fails for the same reason, and the state reaches zero. Only after exhausting that proved border chain should the scan consume the character or accept it as a new one-character prefix.

That narration gives the interviewer a correctness proof in miniature. No possible alignment was skipped: every surviving alignment must end at the current text position and must also be a border of the prefix already matched. The prefix table enumerates exactly those candidates from longest to shortest. This explanation is more valuable than drawing arbitrary arrows because it connects each array lookup to a previously proved equality.

Diagnose the bug from the failed example

Use a small adversarial case rather than staring at the full loop:

These tests are article-specific tools: they connect an observed failure to the exact KMP state transition that caused it. They also give you a concise explanation during an interview: reproduce, name the violated invariant, and make one bounded correction.

Choose the matcher from the contract

Algorithm choice is an engineering inference, not an employer rule:

The original Aho-Corasick work generalizes failure transitions across a trie of patterns. PracHub’s multi-source string matching and tagging is a concrete drill: it requires all overlapping outputs and contributor intervals, so running a single-pattern search independently may repeat too much work. Highlight Exact Source Matches adds interval merging after detection. Separate those phases: matching produces half-open intervals; a later sweep merges coverage.

Clarify characters, bytes, and indexes

KMP only requires a sequence with consistent equality, but the returned index depends on what one element means. ASCII bytes, Unicode code points, and user-perceived grapheme clusters are different units. In Python, string indexing uses Unicode code points; in UTF-8 byte buffers, an index is a byte offset. Normalization can also make visually identical text compare unequal.

Ask what the API promises. If exact binary matching is required, compare bytes and return byte offsets. If user-visible text equivalence matters, define normalization before building the prefix table and decide whether results refer to normalized or original text. Do not say “KMP handles Unicode” without naming the unit and mapping rule.

Practice five related PracHub questions

Each record below exercises a different contract. They are practice material, not a forecast of the reader’s interview.

Final takeaway

The strongest KMP answer is a state argument, not a memorized pair of loops. Define each prefix entry as a reusable border length. On mismatch, follow the border chain without rewinding the text. After a full match, follow the same chain so overlapping occurrences remain possible. Then prove linear work by charging every fallback against an earlier state increase.

Practice by drawing ababaca and explaining why the c mismatch falls from three to one to zero. Then run aaa over aaaaa and explain why the post-match state remains two. Once those two traces are natural, use the five linked Coding & Algorithms questions to vary the contract before looking at a solution.

Sources and Further Reading

• Knuth, Morris, and Pratt, Fast Pattern Matching in Strings (1977)
• Princeton Algorithms 4/e: KMP
• CP-Algorithms: Prefix function
• Aho and Corasick, Efficient string matching (1975)
• PracHub: Implement string matching with follow-up

Research note: Technical sources and PracHub practice records were checked on September 12, 2026. The sources establish algorithm behavior and individual practice contracts; they do not establish a universal employer interview sequence.