KMP Pattern Matching Algorithm: Complete Implementation Guide

1. Introduction and Core Concepts

The kmp pattern matching algorithm, named after its inventors Donald Knuth, James H. Morris, and Vaughan Pratt, is one of the most elegant and efficient solutions to the classic string searching problem. Given a long text of length n and a pattern of length m, the task is to determine whether the pattern occurs in the text and, if so, where. While this sounds simple, it is a fundamental operation that underpins everything from text editors and search engines to DNA sequencing and network security.

Before KMP, the most intuitive approach was the naive or brute-force method: slide the pattern over the text one position at a time and compare character by character. If a mismatch occurs, shift the pattern by one and start over from the beginning of the pattern. This approach is easy to implement but catastrophically inefficient in the worst case, requiring O(n * m) comparisons. For example, searching for a pattern like "AAAAAB" in a text like "AAAAAAAAAAAAAAAAAB" causes the naive algorithm to repeatedly re-examine the same characters, leading to quadratic time complexity that becomes unacceptable for large inputs.

The core innovation of the kmp pattern matching algorithm is its ability to avoid redundant comparisons. It achieves this by preprocessing the pattern to learn about its internal structure, specifically its self-overlapping properties. KMP never moves backwards in the text; it scans the text exactly once from left to right. When a mismatch occurs, it uses precomputed information to determine the maximum safe shift for the pattern, skipping comparisons that are guaranteed to fail. This single insight transforms a quadratic algorithm into a linear one.

What Makes KMP Different?

The key concept behind KMP is the Longest Proper Prefix which is also Suffix, often abbreviated as LPS. A proper prefix of a string is a prefix that is not equal to the string itself. For any prefix of the pattern, the LPS value tells us the length of the longest proper prefix of that prefix that is also a suffix of that prefix. This value encodes how much of the pattern we can reuse after a mismatch.

Consider the pattern "ABABAC". Its prefix "ABABA" has a proper prefix "ABA" that is also its suffix. This means if we have matched "ABABA" and then fail on the next character, we know that the suffix "ABA" of what we just matched is also a prefix of the pattern, so we can resume comparison without re-scanning the text. The kmp pattern matching algorithm formalizes this intuition into a deterministic automaton that runs in linear time.

Why It Matters Today

In an era of massive data, linear-time string matching is not a luxury but a necessity. Web servers need to route requests by matching URL patterns, databases execute LIKE queries over millions of rows, and intrusion detection systems scan network packets for malicious signatures in real time. In all these scenarios, the guarantee of O(n + m) worst-case performance, as provided by KMP, is critical. Unlike heuristic algorithms that are fast on average but slow in the worst case, KMP offers predictable, optimal performance, making it a cornerstone of string algorithms taught in every advanced algorithms course.

2. How It Works

The kmp pattern matching algorithm operates in two distinct phases: preprocessing and searching. The preprocessing phase analyzes the pattern alone and builds an auxiliary array, commonly called the LPS array, prefix function, or failure function. The searching phase then uses this array to efficiently scan the text. Decoupling these phases is what allows KMP to be so efficient, as the work done on the pattern is reused for every position in the text.

The algorithm maintains two pointers: one for the text and one for the pattern. Unlike the naive approach, the text pointer never decrements. The pattern pointer advances when characters match and retreats intelligently via the LPS array when they do not. This one-way traversal of the text is the source of its linear time bound and its suitability for streaming data where you cannot go backwards.

The Prefix Function (LPS Array)

The LPS array, denoted as lps[i], stores the length of the longest proper prefix of the substring pattern[0..i] which is also a suffix of that substring. By definition, lps[0] is always 0. For example, for pattern "ABABCABAB", the LPS array is [0, 0, 1, 2, 0, 1, 2, 3, 4]. The value lps[3] = 2 means the prefix "ABAB" has "AB" as both prefix and suffix.

Computing this array efficiently is itself a clever application of the same principle. We build it incrementally. We keep a length variable representing the length of the previous longest prefix suffix. To compute lps[i], we compare pattern[i] with pattern[length]. If they match, we extend the length and set lps[i] = length. If they mismatch and length is not zero, we fall back to lps[length - 1] without incrementing i, effectively trying a shorter border. This process is linear because length only increases O(m) times.

The Search Phase Mechanism

During the search, suppose we have matched j characters of the pattern against the text and the next characters mismatch: text[i] != pattern[j]. In the naive algorithm, we would reset j to 0 and increment i by one. KMP instead consults lps[j - 1]. This value tells us that the first lps[j - 1] characters of the pattern already match the suffix ending at text[i - 1]. Therefore, we can set j = lps[j - 1] and keep i unchanged, attempting to extend this shorter prefix.

If j is 0 and we still have a mismatch, it means no prefix of the pattern matches the current text position, so we simply advance i by one. When j == m, we have found a full occurrence of the pattern ending at i - 1. To find overlapping occurrences, we do not reset j to 0; we set j = lps[j - 1] and continue, allowing the algorithm to find patterns like "AAA" inside "AAAAA" correctly.

Intuition: The Automaton View

Another way to understand KMP is as a deterministic finite automaton (DFA). Each state represents the number of characters of the pattern matched so far (0 to m). Transitions on a matching character go to the next state; transitions on a mismatching character go to the state indicated by the LPS array. This automaton is built solely from the pattern and then run over the text in a single pass. This view clarifies why KMP never backtracks in the text: the automaton state encapsulates all necessary history.

3. Implementation

Implementing the kmp pattern matching algorithm correctly requires careful handling of indices and edge cases. Below is a modular Python implementation broken into two functions: one to compute the LPS array and one to perform the search. This separation improves readability and reusability, as the LPS array can be precomputed once and used for multiple searches with the same pattern.

Building the LPS Array

The following function computes the prefix function in O(m) time and O(m) space. Pay close attention to the fallback logic when a mismatch occurs. The while loop does not always increment i, which is essential for correctness.

def compute_lps_array(pattern):
    """
    Compute the Longest Proper Prefix which is also Suffix (LPS) array.
    lps[i] = length of longest proper prefix of pattern[0..i] 
             which is also a suffix of pattern[0..i]
    """
    m = len(pattern)
    if m == 0:
        return []
    
    lps = [0] * m
    length = 0  # length of previous longest prefix suffix
    i = 1

    # Loop calculates lps[i] for i from 1 to m-1
    while i < m:
        if pattern[i] == pattern[length]:
            # Characters match, extend the border
            length += 1
            lps[i] = length
            i += 1
        else:
            # Mismatch
            if length != 0:
                # Fall back to the previous longest border
                # Do not increment i here
                length = lps[length - 1]
            else:
                # No border exists for this prefix
                lps[i] = 0
                i += 1
    return lps

The Main Search Loop

The search function uses the LPS array to find all occurrences of the pattern in the text. It returns a list of starting indices where the pattern is found. Note how the text index i is only incremented on a match or when j == 0, and how j is updated using the LPS array on mismatch.

def kmp_search(text, pattern):
    """
    Search for pattern in text using KMP algorithm.
    Returns list of starting indices where pattern is found.
    Time: O(n + m), Space: O(m)
    """
    n = len(text)
    m = len(pattern)
    
    if m == 0:
        return []
    if n < m:
        return []

    lps = compute_lps_array(pattern)
    occurrences = []
    
    i = 0  # index for text
    j = 0  # index for pattern

    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1

            # Found a complete match
            if j == m:
                occurrences.append(i - j)
                # Allow overlapping matches
                j = lps[j - 1]
        else:
            # Mismatch after j matches
            if j != 0:
                # Use LPS to skip comparisons
                j = lps[j - 1]
                # Note: i is NOT incremented here
            else:
                # No characters matched, move to next text character
                i += 1
                
    return occurrences

Complete Implementation with Edge Cases

For production use, you should handle empty strings, Unicode, and provide a simple boolean or first-occurrence wrapper. The following complete example adds input validation and a helper to find just the first match, which can terminate early for better average-case performance.

def kmp_first_occurrence(text, pattern):
    """Return index of first occurrence or -1 if not found."""
    if not pattern:
        return 0  # Empty pattern matches at start by convention
    if not text or len(pattern) > len(text):
        return -1

    lps = compute_lps_array(pattern)
    i = j = 0
    n, m = len(text), len(pattern)

    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                return i - j  # First match found
        else:
            if j > 0:
                j = lps[j - 1]
            else:
                i += 1
    return -1

# Example usage
if __name__ == "__main__":
    text = "ABABDABACDABABCABAB"
    pattern = "ABABCABAB"
    print(f"LPS for '{pattern}': {compute_lps_array(pattern)}")
    print(f"All occurrences: {kmp_search(text, pattern)}")
    print(f"First occurrence: {kmp_first_occurrence(text, pattern)}")

Object-Oriented Variant for Reusability

When searching for the same pattern in many texts, it is wasteful to recompute the LPS array each time. An object-oriented design precomputes the LPS once in the constructor. This is how KMP is used in real systems like log analyzers that scan millions of lines for a fixed set of patterns.

class KMPMatcher:
    """Reusable KMP matcher that precomputes LPS once."""
    def __init__(self, pattern):
        self.pattern = pattern
        self.m = len(pattern)
        self.lps = compute_lps_array(pattern) if pattern else []

    def search_in(self, text):
        """Search pattern in given text, return all start indices."""
        if self.m == 0:
            return list(range(len(text) + 1))
        return kmp_search(text, self.pattern)

    def contains(self, text):
        """Check if pattern exists in text (early exit)."""
        return kmp_first_occurrence(text, self.pattern) != -1

# Reuse matcher for multiple texts
matcher = KMPMatcher("error")
logs = ["info: ok", "error: disk full", "warning: error threshold"]
for log in logs:
    if matcher.contains(log):
        print(f"Found in: {log}")

4. Step-by-Step Example

To solidify understanding, let us walk through the kmp pattern matching algorithm with a concrete example. This detailed trace shows exactly how the LPS array prevents unnecessary work. We will search for pattern P = "ABABCABAB" in text T = "ABABABABCABABABABCABAB". This example is chosen because the pattern has significant self-overlap.

Step 1: Preprocess the Pattern and Build LPS

We first compute the LPS array for P = "ABABCABAB" (m=9). We initialize lps[0]=0, length=0, i=1.

• i=1, P[1]='B' vs P[0]='A' -> mismatch, length==0 so lps[1]=0, i=2
• i=2, P[2]='A' vs P[0]='A' -> match, length=1, lps[2]=1, i=3
• i=3, P[3]='B' vs P[1]='B' -> match, length=2, lps[3]=2, i=4
• i=4, P[4]='C' vs P[2]='A' -> mismatch, length=2 -> length=lps[1]=0, now P[4]='C' vs P[0]='A' mismatch, lps[4]=0, i=5
• i=5, P[5]='A' vs P[0]='A' -> match, length=1, lps[5]=1, i=6
• i=6, P[6]='B' vs P[1]='B' -> match, length=2, lps[6]=2, i=7
• i=7, P[7]='A' vs P[2]='A' -> match, length=3, lps[7]=3, i=8
• i=8, P[8]='B' vs P[3]='B' -> match, length=4, lps[8]=4, i=9 (done)

Final LPS = [0, 0, 1, 2, 0, 1, 2, 3, 4]. This tells us that the whole pattern has a border "ABAB" of length 4.

Step 2: Search Through the Text

Now we scan T. We will highlight a critical moment where KMP saves work. Let i be text index, j pattern index.

1. We match "ABAB" successfully: T[0..3]="ABAB" == P[0..3], so i=4, j=4. Next, T[4]='A' vs P[4]='C' -> mismatch.
2. Naive would shift by 1 and restart at T[1]. KMP does j = lps[3] = 2. So j becomes 2, i stays at 4. This means we keep the suffix "AB" of the matched "ABAB" as the new prefix.
3. Now compare T[4]='A' vs P[2]='A' -> match, i=5, j=3. T[5]='B' vs P[3]='B' -> match, i=6, j=4. Again T[6]='A' vs P[4]='C' -> mismatch.
4. Again j = lps[3]=2, compare T[6]='A' vs P[2]='A' -> match, and continue. This process continues, never moving i backwards.
5. Eventually at i=9, j=9 we find a full match ending at i=9. The start index is i - j = 0? Let's trace more accurately: the first full match of "ABABCABAB" actually occurs at T[4..12]? In our text "ABABABABCABAB...", the pattern is found at index 4 and again later. The algorithm correctly finds both by setting j = lps[8]=4 after each match to allow overlaps.

The key takeaway is that after each mismatch, KMP reuses the already-matched suffix. In this trace, we saved 2 character comparisons at each of the first two mismatches. Over a long text with repetitive structure, these savings accumulate to linear time, while naive would re-compare the same "AB" prefix many times.

Visualizing the Shift

Imagine aligning pattern under text. When mismatch happens at position j, the LPS value tells us how far to slide the pattern to the right so that the prefix of length lps[j-1] aligns with the suffix that just matched. No characters of the text are re-examined. This is why KMP is called a "left-to-right" scan and is optimal for streaming inputs where the text arrives character by character.

5. Complexity Analysis

One of the primary reasons to choose the kmp pattern matching algorithm is its strong theoretical guarantees. Unlike many string algorithms that have good average-case performance but degrade to quadratic worst-case, KMP guarantees linear time in all cases. Understanding its complexity is essential for system design and for answering interview questions.

Time Complexity Breakdown

The algorithm consists of two phases. The preprocessing phase that builds the LPS array runs in O(m) time, where m is the pattern length. This is because the variable length only increases at most m times and the fallback via lps[length-1] strictly decreases it, so the total number of iterations is bounded by 2*m.

The searching phase runs in O(n) time, where n is the text length. The text pointer i advances at most n times (once per successful match or when j==0). The pattern pointer j can be decremented via the LPS array, but each such decrement strictly reduces j, and j can only be incremented n times total (once per i increment). Thus the total work is O(n). Combined, the overall time is O(n + m), which is asymptotically optimal since any algorithm must at least read both strings.

Space Complexity

KMP requires O(m) additional space to store the LPS array. The text itself is not copied, and only a few integer pointers are used. This makes it very memory efficient, especially compared to algorithms like Aho-Corasick or suffix automata that may require larger automata. For extremely large alphabets or patterns, the O(m) space is negligible.

There is also an optimized version that can be implemented with O(1) extra space if the pattern is processed on the fly, but the standard formulation with an explicit LPS array is clearer and still optimal for most use cases.

Best, Average, and Worst Case Nuances

For KMP, best, average, and worst cases are all linear, which is a rare and valuable property. The best case still requires scanning the entire text, so it is O(n). The worst case, such as searching for "AAAAB" in "AAAAAAAAAA...", is where KMP dramatically outperforms naive. Naive would take O(n*m) here, while KMP remains O(n). This predictability makes KMP ideal for real-time systems where worst-case latency must be bounded, such as intrusion detection or real-time log monitoring.

6. Variations and Optimizations

The classic kmp pattern matching algorithm is already optimal in asymptotic terms, but several practical variations and optimizations exist to improve constant factors, handle special cases, or extend its functionality. Understanding these variants demonstrates deeper mastery and is useful when adapting KMP to specific constraints.

Optimized LPS (Strong Prefix Function)

The standard LPS array can be slightly optimized to avoid a redundant comparison. If pattern[j] == pattern[lps[j-1]], then after a mismatch at j, falling back to lps[j-1] will immediately cause another mismatch. The optimized version, sometimes called the "strong" prefix function or "next" array in some textbooks, checks this condition and, if true, sets lps[j] = lps[lps[j-1]] instead. This can save up to one comparison per mismatch, though the asymptotic complexity remains the same. In practice, the gain is small and the code becomes more complex, so the standard version is usually preferred for clarity.

KMP for Multiple Patterns and Streaming

When searching for many patterns simultaneously, KMP can be extended into the Aho-Corasick algorithm, which builds a trie of patterns augmented with failure links analogous to the LPS array. For a single pattern in a streaming context, KMP is naturally suited because it processes the text one character at a time without needing to buffer the entire text. You can feed characters from a network socket or file as they arrive, maintaining only i, j, and the LPS array.

Memory and Cache Optimizations

For very large alphabets or binary data, the LPS array of integers may be cache-unfriendly. Some implementations store the LPS as an array of shorts if m < 65535, halving memory. Another optimization is to combine the LPS computation and search into a single pass when the pattern is small, avoiding a separate allocation. In Python, using lists of ints is fine, but in C/C++ for high-performance packet scanning, these micro-optimizations matter.

When Not to Optimize

For most Python applications, the standard implementation is sufficient. Python's string find (which uses a mix of algorithms including Two-Way and BMH) is implemented in C and will outperform pure Python KMP for short patterns. Use KMP in Python when you need to understand or customize the matching logic, handle overlapping matches explicitly, or when teaching the algorithm. For production performance on huge texts, consider using Python's built-in re or find for single queries, and reserve KMP for educational or specialized streaming scenarios.

7. Real-World Applications

While the kmp pattern matching algorithm may seem like a purely academic exercise, it powers numerous real-world systems where reliable, linear-time string searching is non-negotiable. Its guarantee of no backtracking makes it especially valuable in environments where data is streamed or where worst-case performance must be bounded.

In web servers and application frameworks, routing engines match incoming URLs against a set of route patterns. Although many routers use tries or regex, KMP-like logic is used for efficiently matching static prefixes and for scanning HTTP headers for delimiters. Similarly, web application firewalls (WAFs) scan request bodies for known attack signatures, such as SQL injection payloads, where missing a pattern due to a worst-case blowup could be a security vulnerability.

Databases use string matching extensively for LIKE '%pattern%' queries, full-text search, and for parsing SQL itself. While databases often use indexes like B-trees or inverted indexes to avoid scanning, when a scan is necessary, a linear algorithm like KMP ensures predictable query time. Bioinformatics is another major domain: searching for a gene sequence (pattern) inside a genome (text) involves texts of billions of characters. An O(n*m) algorithm would be infeasible; KMP's O(n+m) is essential.

Case Study: Intrusion Detection Systems

Consider Snort or Suricata, open-source intrusion detection systems that inspect every network packet for thousands of attack signatures. Packets arrive at line rate (10-100 Gbps) and must be scanned in real time. These systems cannot afford an algorithm that degrades to O(n*m) on adversarial input crafted to trigger worst-case behavior. KMP and its multi-pattern extension Aho-Corasick provide the deterministic performance needed. The pattern set is preprocessed once, and each packet is scanned in a single pass, making it possible to keep up with high throughput without dropping packets.

Beyond Text: Binary and Unicode

KMP is not limited to ASCII text. It works on any sequence over any alphabet, including bytes, Unicode code points, or even token streams. This generality means it can be used to search for byte patterns in executables, for emoji sequences in social media data, or for sequences of events in log analysis. The algorithm only requires equality comparison, so it is alphabet-agnostic.

8. Comparison with Alternatives

Choosing the right string matching algorithm depends on pattern length, alphabet size, text size, and whether you need worst-case guarantees or average-case speed. The kmp pattern matching algorithm is one of several classic solutions, each with different trade-offs. Understanding these alternatives helps you select the best tool for the job and is a frequent topic in system design interviews.

The naive algorithm is the baseline: simple but slow. Rabin-Karp uses hashing to filter candidates and is excellent for multiple pattern search with average O(n+m) but worst-case O(n*m) due to hash collisions. Boyer-Moore and its variants (Boyer-Moore-Horspool) scan the pattern from right to left and can skip large portions of the text, achieving sublinear time O(n/m) on average for large alphabets, but still O(n*m) worst-case. KMP is the only one among these that guarantees linear worst-case with minimal extra space.

When to Choose Which Algorithm

Use KMP when you need predictable performance, are processing streaming data, or have a small alphabet (like DNA with 4 characters) where Boyer-Moore's skipping is less effective. Use Boyer-Moore when searching for long patterns in natural language text where its ability to skip ahead yields huge speedups in practice; this is why many text editors use BM variants. Use Rabin-Karp when searching for many patterns at once or when you need to find duplicate substrings, as its hashing approach generalizes well.

In Python, the built-in str.find() and re.search() are implemented in C using highly optimized algorithms (often a combination of Two-Way algorithm, which is similar to KMP, and BMH). For most application code, you should use those built-ins for speed. Implement KMP explicitly when you need to customize the matching logic, count overlapping occurrences, or demonstrate algorithmic understanding in an interview or educational setting.

Hybrid Approaches

Modern libraries often use hybrid strategies: they start with a fast heuristic like Horspool to skip ahead, and fall back to KMP-like logic to guarantee linear worst-case. The "Two-Way" algorithm used in CPython and glibc is a sophisticated variant that achieves O(n+m) worst-case with O(1) extra space by combining prefix and suffix analyses. Studying KMP provides the foundation for understanding these more advanced hybrids.

9. Common Mistakes and Best Practices

Implementing the kmp pattern matching algorithm is notoriously tricky for beginners. Off-by-one errors, incorrect LPS construction, and mishandling of edge cases are common. Following best practices will help you write correct, maintainable, and efficient code.

Frequent Pitfalls

• Forgetting to not increment i on fallback: The most common bug is incrementing the text pointer i when you do j = lps[j-1] after a mismatch. The text pointer should stay, as you are re-aligning the pattern, not advancing in the text. Incrementing i here skips a character and misses matches.
• Incorrect LPS initialization: lps[0] must be 0, and the loop must start at i=1. Starting at i=0 or initializing lps with wrong values leads to infinite loops or incorrect shifts.
• Not handling overlapping matches: After finding a match (j == m), many novices reset j to 0. This misses overlapping occurrences. For example, searching for "AAA" in "AAAA" should find matches at 0 and 1. Correct is j = lps[j-1] after a match.
• Confusing < and <= in loop conditions: The search loop is while i < n, not <=. Using <= causes IndexError. Similarly, check j > 0 before accessing lps[j-1].
• Ignoring empty pattern/text: Edge cases like empty pattern, empty text, or pattern longer than text must be handled explicitly to avoid crashes. Define behavior: empty pattern typically matches at every position or at index 0.
• Not escaping < > in HTML contexts: When displaying code on the web, failing to escape < and > breaks HTML rendering. Always use &lt; and &gt; inside code blocks.

Best Practices

• Modularize preprocessing and searching: Keep compute_lps_array separate from kmp_search. This makes testing easier and allows reuse of the LPS for multiple searches.
• Test with repetitive patterns: Always test with patterns that have strong borders like "AAAA", "ABABAB", and "ABCABCABC". These stress the fallback logic and reveal bugs that simple patterns like "ABC" hide.
• Use descriptive variable names: Use text, pattern, lps, i, j consistently. Avoid single-letter confusion by commenting what i and j represent.
• Validate with brute force for small inputs: During testing, compare KMP results against a naive implementation for random small strings to catch subtle errors.
• Document time and space guarantees: Add docstrings stating O(n+m) time and O(m) space so future maintainers understand the performance contract.
• Consider Python's built-ins for production: If you do not need custom logic, prefer str.find or regex for raw speed, as they are implemented in C. Use KMP when you need its specific guarantees or educational value.

Debugging Tip: Print the LPS Array

When debugging, print the LPS array for your pattern and manually trace a few steps. If the LPS looks wrong, the search will be wrong. For pattern "ABACABAB", the correct LPS is [0,0,1,0,1,2,3,2]. If you get [0,0,1,0,1,2,2,3], you know the fallback logic is flawed. Visualizing the alignment of pattern shifts on paper also helps catch logic errors quickly.

10. Interview Questions

The kmp pattern matching algorithm is a favorite in technical interviews for software engineering and graduate school admissions because it tests understanding of preprocessing, amortized analysis, and careful pointer manipulation. Below are common questions with concise answer strategies.

Q1: Implement KMP to Return All Occurrences (Including Overlaps)

This is the standard coding question. Interviewers expect you to write both compute_lps and kmp_search correctly and handle overlaps. Emphasize that after finding a match at i - j, you set j = lps[j-1] instead of 0. Be ready to explain why this works and to analyze complexity as O(n+m) time and O(m) space. A common follow-up is to modify the code to return only the first occurrence with early termination.

Q2: Why Does KMP Achieve O(n) Search Time? Prove It.

Answer with amortized analysis. The text pointer i increases at most n times. The pattern pointer j increases at most n times (once per i increment) and decreases only via lps, which strictly reduces j. Each decrease can be charged to a previous increase, so total decrements are also O(n). Therefore total operations are O(n). Contrast this with naive where i can move backwards, leading to O(n*m). Mention that preprocessing is O(m) by similar reasoning, so overall O(n+m).

Q3: What Is the LPS Array for "AABAACAABAA" and How Is It Built?

This tests your ability to compute LPS manually. For "AABAACAABAA" (length 11), the LPS is [0,1,0,1,2,0,1,2,3,4,5]. Walk through the construction: show how you extend when characters match and fall back via lps[length-1] when they mismatch. Interviewers often ask you to compute it on the board without code to verify you understand the definition of proper prefix/suffix. Practice with patterns like "ABABCABAB" and "AAAA" beforehand.

Q4: How Would You Modify KMP to Search for Multiple Patterns Efficiently?

The expected answer is to discuss the Aho-Corasick algorithm, which generalizes KMP's failure function to a trie. Explain that you build a trie of all patterns, then add failure links (analogous to LPS) that point to the longest proper suffix that is also a prefix of some pattern. Then you scan the text once in O(n + total pattern length + number of matches). If you only have a few patterns, you could also run KMP multiple times, but that is O(k*(n+m)) and less efficient than Aho-Corasick for large k.

Q5: When Would You Prefer Boyer-Moore Over KMP, and Vice Versa?

This evaluates system design judgment. Answer: Prefer Boyer-Moore when the alphabet is large and patterns are long, because its right-to-left scanning and bad-character heuristic allow it to skip many characters, often achieving sublinear average time. Prefer KMP when you need guaranteed linear worst-case, are processing streaming data where you cannot look ahead, have a small alphabet (e.g., binary or DNA), or need to find overlapping matches reliably. Mention that Python's built-in find uses a hybrid (Two-Way) that gives KMP-like guarantees with Boyer-Moore-like speed in practice.

Preparing answers to these questions with both code and conceptual explanations will demonstrate depth beyond mere memorization. Practice writing KMP from scratch without referencing material, as interviewers often ask for a bug-free implementation under time pressure.