String Matching in Interviews: KMP and Rolling Hash Explained

Why string matching shows up so often

String matching is one of those interview topics that looks simple at first and then quietly tests several core skills at once: careful indexing, loop invariants, edge cases, and the ability to choose the right algorithm under constraints.

A brute-force scan can work for small inputs, but interviewers often want to see whether you know how to avoid repeated work. That is where KMP and Rabin-Karp come in. Both solve the same pattern matching problem, but they do it in very different ways:

• KMP avoids re-checking characters by reusing information about the pattern itself.
• Rabin-Karp uses hashing to compare substrings quickly and only confirms matches when hashes line up.

If you understand both, you can explain tradeoffs clearly and choose the right tool when the constraints change.

Problem statement

Given a text string text and a pattern string pattern, find whether the pattern appears in the text, and optionally return all starting positions where it appears.

Example:

• text = "abxabcabcaby"
• pattern = "abcaby"
• Output: 6

In practice, interview variants may ask you to:

• find the first occurrence
• find all occurrences
• count matches
• support repeated patterns efficiently
• explain the time complexity

Intuition and insight

The brute-force baseline

The simplest approach checks every possible alignment of pattern against text.

For each index i in text, compare pattern[0] with text[i], pattern[1] with text[i+1], and so on.

This works, but in the worst case it repeats a lot of comparisons. For example:

• text = "aaaaaa...aaaaab"
• pattern = "aaaaab"

A naive solution keeps re-checking the same a characters over and over.

KMP insight: reuse matched prefix information

KMP stands for Knuth-Morris-Pratt. Its key idea is this:

If you already matched a prefix of the pattern and then hit a mismatch, don’t start from scratch. Use what you learned about the pattern to shift intelligently.

KMP builds a helper array often called lps:

• lps[i] = length of the longest proper prefix of pattern[:i+1] that is also a suffix of it

This tells you how much of the pattern still matches itself after a mismatch.

Rabin-Karp insight: compare hashes instead of full strings

Rabin-Karp uses a rolling hash:

• hash the current window in the text
• hash the pattern
• if hashes match, compare the actual substring to avoid false positives

The hash can be updated in constant time as the window slides, which makes it efficient for checking many positions.

Rabin-Karp is especially useful when:

• you want to search for multiple patterns
• you need a fast average-case solution
• you can tolerate a small chance of hash collision, with verification

Approach 1: KMP step by step

Step 1: Build the LPS array

Let’s use the pattern "ababaca".

We compute lps for each position:

• a → 0
• ab → 0
• aba → 1
• abab → 2
• ababa → 3
• ababac → 0
• ababaca → 1

So the final array is:

[0, 0, 1, 2, 3, 0, 1]

This array tells us how far we can jump back in the pattern after a mismatch.

Step 2: Scan the text once

We maintain two pointers:

• i for the text
• j for the pattern

Rules:

• if text[i] == pattern[j], advance both
• if j reaches the end of the pattern, we found a match
• if there is a mismatch and j > 0, set j = lps[j - 1]
• if there is a mismatch and j == 0, advance i

Python code: KMP for first occurrence

def build_lps(pattern: str) -> list[int]:
    lps = [0] * len(pattern)
    length = 0  # length of the previous longest prefix suffix
    i = 1

    while i < len(pattern):
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps


def kmp_search(text: str, pattern: str) -> int:
    if not pattern:
        return 0

    lps = build_lps(pattern)
    i = j = 0

    while i < len(text):
        if text[i] == pattern[j]:
            i += 1
            j += 1

            if j == len(pattern):
                return i - j
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

    return -1

Worked example 1: tracing KMP

Suppose:

• text = "abxabcabcaby"
• pattern = "abcaby"

The match appears at index 6.

What KMP avoids:

• after matching "abcab", a mismatch happens
• instead of moving the pattern all the way back to the start, KMP uses the lps array to reuse the fact that "ab" is both a prefix and suffix of the matched segment

That reuse is the entire point. You never move i backward, and you never re-scan characters unnecessarily.

Worked example 2: repeated characters

This is the classic case where KMP shines:

• text = "aaaaaaaaaaaaaaaaab"
• pattern = "aaaaab"

A naive algorithm repeatedly compares the same run of as. KMP builds the prefix knowledge into lps, so when the mismatch at the final b happens, it jumps the pattern pointer back to a meaningful state instead of restarting.

The result is linear time even in this adversarial case.

Approach 2: Rabin-Karp step by step

Step 1: Hash the pattern and the first window

We treat each string as a number in a base, usually with a modulus to keep values manageable.

For a window of size m:

• compute hash for pattern
• compute hash for text[:m]

If the hashes match, compare the actual substring.

Step 2: Slide the window in O(1)

When moving from one window to the next:

• remove the contribution of the leftmost character
• multiply by the base
• add the new rightmost character

This is why it is called a rolling hash.

Python code: Rabin-Karp for first occurrence

def rabin_karp_search(text: str, pattern: str) -> int:
    if not pattern:
        return 0

    n, m = len(text), len(pattern)
    if m > n:
        return -1

    base = 256
    mod = 10**9 + 7

    # base^(m-1) % mod, used to remove the leading character
    high_base = pow(base, m - 1, mod)

    pattern_hash = 0
    window_hash = 0

    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
        window_hash = (window_hash * base + ord(text[i])) % mod

    for i in range(n - m + 1):
        if pattern_hash == window_hash:
            if text[i:i + m] == pattern:
                return i

        if i < n - m:
            left_char = ord(text[i])
            right_char = ord(text[i + m])
            window_hash = (
                (window_hash - left_char * high_base) * base + right_char
            ) % mod

    return -1

Worked example 3: tracing the rolling window

Suppose:

• text = "thequickbrownfox"
• pattern = "brown"

Rabin-Karp hashes every 5-character window:

• thequ
• hequi
• equic
• ...
• brown

Only when the window hash matches the pattern hash do we compare characters directly.

This makes the method efficient when the text is long and the pattern is short, especially if you need to scan many windows.

When to use KMP vs Rabin-Karp

Both are strong interview answers, but they solve slightly different problems.

Complexity analysis

KMP

• Building LPS: O(m)
• Searching: O(n)
• Total: O(n + m)
• Space: O(m) for the LPS array

Why linear? Because each character in the text and pattern moves forward in a controlled way. The algorithm never backtracks in the text.

Rabin-Karp

• Initial hash computation: O(m)
• Sliding through the text: O(n) average
• Verification after hash match: usually rare, but can degrade in worst cases

Average-case total: O(n + m) Worst-case total: O(nm) if many collisions force repeated substring checks.

Space is typically O(1) beyond the input, though some variants keep more state.

Common interview pitfalls

• Forgetting empty pattern behavior: decide whether to return 0 or all positions.
• Off-by-one errors in LPS: lps[j - 1], not lps[j].
• Not verifying Rabin-Karp hash matches: hashes can collide.
• Using too small a modulus: increases collision risk.
• Resetting the text pointer in KMP: that breaks the linear-time guarantee.

Related problems

Once you understand string matching, several interview problems become easier:

• finding all occurrences of a pattern in a text
• repeated substring pattern
• shortest palindrome
• valid anagram windows
• substring search with constraints
• DNA sequence matching and log scanning variants

A lot of “sliding window” problems are not true pattern matching, but they share the same habit: you keep state across adjacent windows instead of recomputing from scratch.

Quick comparison with code behavior

Here is a compact way to think about the two algorithms:

• KMP is about structure in the pattern.
• Rabin-Karp is about compressing the window into a hash.

If the interviewer asks for guaranteed performance, KMP is often the safer choice. If they ask about multiple patterns or rolling checks, Rabin-Karp is worth discussing.

Key takeaways

• String matching is a classic interview topic because it tests both algorithmic insight and implementation discipline.
• KMP avoids re-checking characters by using the LPS array.
• Rabin-Karp uses rolling hashes to compare substrings efficiently.
• KMP gives deterministic linear time.
• Rabin-Karp has great average-case behavior, but you must verify hash matches.
• In interviews, explain not just the code, but why each algorithm avoids repeated work.

If you want to see the pointers, hashes, and prefix values update one step at a time, I built an interactive version of this walkthrough at codebrew.ai — might help if you’re a visual learner.

Practice these next

Try these problems to reinforce the pattern:

1. Implement strStr() / find first occurrence of a substring
2. Find all occurrences of a pattern in a text
3. Repeated Substring Pattern
4. Shortest Palindrome
5. Implement wildcard or regex-style matching basics