Building the Failure… — KMP Algorithm — Failure… | OneNoughtOne

0/97

Data Structures & AlgorithmsKMP Algorithm

KMP Algorithm — Failure Function & Matching

LevelIntermediate

Duration75 mins

TopicKMP Algorithm

5 / 5

Building the Failure Function

The Self-Referential Elegance

We've seen what the LPS array contains and how it enables efficient pattern matching. But how do we build the LPS array efficiently? The naive approach would be: for each position i, try all possible prefix lengths and check if they match the corresponding suffix. This would be O(m³) or O(m²) with optimization—far too slow for large patterns. The breakthrough insight is beautiful in its self-reference: we use the same pattern-matching technique to build the LPS array that we'll later use for text matching . The pattern becomes both the "text" and the "pattern" in a brilliant recursive construction. This is one of the most elegant algorithms in computer science—efficient, correct, and conceptually deep.

What You Will Learn

By the end of this page, you will understand the complete LPS construction algorithm, why it works, and how to implement it. You'll see the elegant recursion that makes O(m) possible and be able to trace the algorithm by hand.

The Naive Approach — Why It's Too Slow

Before appreciating the efficient algorithm, let's understand why the obvious approach fails. Naive Algorithm: def naive_lps(pattern): m = len(pattern) lps = [0] * m for i in range(1, m): # For each position i, find longest proper prefix = suffix for length in range(i, 0, -1): # Try longest first prefix = pattern[0:length] suffix = pattern[i-length+1:i+1] if prefix == suffix: lps[i] = length break return lps Complexity Analysis: Outer loop: m iterations Inner loop: up to i iterations (checking lengths from i down to 1) String comparison: up to i characters each Total: O(m³) in the worst case For a pattern of 100,000 characters, this is 10¹⁵ operations—completely impractical.

The Redundancy Problem

The naive algorithm repeatedly compares the same substrings. If we've determined that 'ABAB' has LPS of 2 ('AB' matches), why should we re-examine 'AB' when computing the next LPS value? This redundancy is exactly what KMP's construction algorithm eliminates.

The Key Insight — Building Incrementally

The efficient construction uses a powerful observation: If we know LPS[i-1], we can compute LPS[i] by trying to extend the previous overlap. Let's say LPS[i-1] = k. This means: pattern[0..k-1] = pattern[i-k..i-1] The first k characters equal the last k characters of pattern[0..i-1] Now we want LPS[i]. There are two cases: Case 1: pattern[k] == pattern[i] The overlap extends! We have: pattern[0..k] = pattern[i-k..i] LPS[i] = k + 1

extend_case.txt
EXTENDING AN OVERLAP
 
Previous state: pattern[0..i-1], LPS[i-1] = k
 
Pattern: ... [0] [1] ... [k-1] [k] ... [i-k] [i-k+1] ... [i-1] [i]
              └─── prefix (k chars) ───┘    └──── suffix (k chars) ────┘
                        ↑                           ↑
                    These are equal (LPS[i-1] = k)
 
Now checking if pattern[k] == pattern[i]:
 
Pattern: ... [0] [1] ... [k-1] [k] ... [i-k] [i-k+1] ... [i-1] [i]
                              ↑                               ↑
                        pattern[k]                       pattern[i]
 
If they're equal:
- pattern[0..k] = pattern[i-k..i]
- The k-length overlap becomes (k+1)-length
- LPS[i] = k + 1

Case 2: pattern[k] != pattern[i] The overlap doesn't extend. But we shouldn't give up—there might be a shorter overlap that we can extend. Here's the key: the next candidate length to try is LPS[k-1] . Why? Because LPS[k-1] is the longest proper prefix of pattern[0..k-1] that equals a suffix. And since pattern[0..k-1] equals a suffix of what we're building, this "nested" overlap might extend to include pattern[i].

The Recursive Insight

When extension fails, we "fall back" to LPS[k-1] and try again. This is the exact same fallback logic that happens during matching! We're matching the pattern against itself, using previously computed LPS values.

The Complete Algorithm

Here's the complete, efficient LPS construction algorithm:

lps_construction.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def compute_lps(pattern: str) -> list[int]:
    """
    Compute the LPS (Longest Proper Prefix which is also Suffix) array.
    
    Time Complexity: O(m) where m = len(pattern)
    Space Complexity: O(m) for the LPS array
    
    Args:
        pattern: The pattern string to preprocess
        
    Returns:
        LPS array where LPS[i] = length of longest proper prefix of 
        pattern[0..i] that is also a suffix of pattern[0..i]
    """
    m = len(pattern)
    
    if m == 0:
        return []
    
    lps = [0] * m  # LPS[0] is always 0 (no proper prefix for single char)
    
    # 'length' tracks the length of the current longest prefix-suffix
    # Think of it as: "I have matched 'length' characters of the prefix"
    length = 0
    
    # Start from index 1 (LPS[0] = 0 is given)
    i = 1
    
    while i < m:
        if pattern[i] == pattern[length]:
            # Extension successful!
            # The prefix pattern[0..length] matches suffix ending at i
            length += 1
            lps[i] = length
            i += 1
            
        else:
            # Extension failed
            if length > 0:
                # Fall back to the next candidate: LPS[length-1]
                # This is the "nested" overlap within our current overlap
                length = lps[length - 1]
                # NOTE: we do NOT increment i here - we retry with shorter length
                
            else:
                # length is 0, no prefix matches
                lps[i] = 0
                i += 1
    
    return lps

Key Points in the Algorithm: length variable: Tracks how many characters of prefix we've matched to suffix. Extension (line 30-33): When pattern[i] matches pattern[length], we've extended our prefix-suffix match. Fallback (line 38): When extension fails but length > 0, we use the LPS value at position length-1 to find the next candidate. Not incrementing i during fallback: This is crucial! We keep trying shorter overlaps at the same position i until we either find one that extends, or exhaust all possibilities (length becomes 0). Reset (lines 41-43): When length = 0 and we still mismatch, there's no prefix-suffix—LPS[i] = 0.

Detailed Trace Through Examples

Let's trace through the algorithm with several patterns to deeply understand how it works. Example 1: Pattern "ABCAB"

trace_abcab.txt
Pattern: A B C A B
Index:   0 1 2 3 4
 
Initialize: lps = [0, 0, 0, 0, 0], length = 0, i = 1
 
─────────────────────────────────────────────────────────
 
i = 1, length = 0:
Compare pattern[1]='B' with pattern[0]='A': NOT EQUAL
length = 0, so: lps[1] = 0, i++
→ lps = [0, 0, 0, 0, 0], length = 0, i = 2
 
─────────────────────────────────────────────────────────
 
i = 2, length = 0:
Compare pattern[2]='C' with pattern[0]='A': NOT EQUAL
length = 0, so: lps[2] = 0, i++
→ lps = [0, 0, 0, 0, 0], length = 0, i = 3
 
─────────────────────────────────────────────────────────
 
i = 3, length = 0:
Compare pattern[3]='A' with pattern[0]='A': EQUAL ✓
length++, lps[3] = 1, i++
→ lps = [0, 0, 0, 1, 0], length = 1, i = 4
 
─────────────────────────────────────────────────────────
 
i = 4, length = 1:
Compare pattern[4]='B' with pattern[1]='B': EQUAL ✓
length++, lps[4] = 2, i++
→ lps = [0, 0, 0, 1, 2], length = 2, i = 5
 
─────────────────────────────────────────────────────────
 
i = 5 = m, DONE!
 
FINAL: LPS = [0, 0, 0, 1, 2]

Example 2: Pattern "AABAAAB" (with fallbacks)

trace_aabaaab.txt
Pattern: A A B A A A B
Index:   0 1 2 3 4 5 6
 
Initialize: lps = [0, 0, 0, 0, 0, 0, 0], length = 0, i = 1
 
─────────────────────────────────────────────────────────
 
i = 1, length = 0:
Compare pattern[1]='A' with pattern[0]='A': EQUAL ✓
length = 1, lps[1] = 1, i = 2
→ lps = [0, 1, 0, 0, 0, 0, 0]
 
─────────────────────────────────────────────────────────
 
i = 2, length = 1:
Compare pattern[2]='B' with pattern[1]='A': NOT EQUAL
length > 0, so fallback: length = lps[0] = 0
(i stays at 2)
 
length = 0:
Compare pattern[2]='B' with pattern[0]='A': NOT EQUAL
length = 0, so: lps[2] = 0, i = 3
→ lps = [0, 1, 0, 0, 0, 0, 0]
 
─────────────────────────────────────────────────────────
 
i = 3, length = 0:
Compare pattern[3]='A' with pattern[0]='A': EQUAL ✓
length = 1, lps[3] = 1, i = 4
→ lps = [0, 1, 0, 1, 0, 0, 0]
 
─────────────────────────────────────────────────────────
 
i = 4, length = 1:
Compare pattern[4]='A' with pattern[1]='A': EQUAL ✓
length = 2, lps[4] = 2, i = 5
→ lps = [0, 1, 0, 1, 2, 0, 0]
 
─────────────────────────────────────────────────────────
 
i = 5, length = 2:
Compare pattern[5]='A' with pattern[2]='B': NOT EQUAL
length > 0, so fallback: length = lps[1] = 1
(i stays at 5)
 
length = 1:
Compare pattern[5]='A' with pattern[1]='A': EQUAL ✓
length = 2, lps[5] = 2, i = 6
→ lps = [0, 1, 0, 1, 2, 2, 0]
 
─────────────────────────────────────────────────────────
 
i = 6, length = 2:
Compare pattern[6]='B' with pattern[2]='B': EQUAL ✓
length = 3, lps[6] = 3, i = 7
→ lps = [0, 1, 0, 1, 2, 2, 3]
 
─────────────────────────────────────────────────────────
 
i = 7 = m, DONE!
 
FINAL: LPS = [0, 1, 0, 1, 2, 2, 3]
 
NOTE: At i=5, we had a FALLBACK.
pattern[5..5] = "A" didn't extend the "AA" overlap (position 2 is 'B').
But after falling back, "A" DID extend the "A" overlap.
lps[5] = 2 means "AA" (prefix) matches "AA" (the last two A's at positions 4,5).

Watch the Fallback Carefully

At position 5, we tried to extend the 'AAB' prefix, failed, fell back to extending 'A', and succeeded. This is the power of the recursive fallback—it finds the best possible overlap without restarting from scratch.

Why the Fallback Logic Works

The fallback length = lps[length - 1] might seem magical. Let's prove it's correct. Claim: When we can't extend a length-k overlap to include pattern[i], the next candidate overlap to try is of length lps[k-1]. Proof: We have: pattern[0..k-1] = pattern[i-k..i-1] (our current k-length overlap) pattern[k] \neq pattern[i] (extension failed) We're looking for a shorter prefix that could extend. Suppose there's a length-j overlap (j < k) that can extend: pattern[0..j-1] = pattern[i-j..i-1] pattern[j] = pattern[i] (extension succeeds) Question: What are the valid candidates for j? Since pattern[0..j-1] must equal pattern[i-j..i-1], and we know pattern[0..k-1] = pattern[i-k..i-1], the substring pattern[i-j..i-1] is a suffix of both: A suffix of pattern[0..i-1] Therefore a suffix of pattern[0..k-1] (since last k chars are our known overlap) So pattern[0..j-1] must be both: A prefix of the pattern A suffix of pattern[0..k-1] (our previous overlap region) This is exactly the definition of "proper prefix of pattern[0..k-1] that is also a suffix"—which is what lps[k-1] measures!

The Largest Valid Candidate

lps[k-1] is the LONGEST prefix of pattern[0..k-1] that is also a suffix. If this can't extend to include pattern[i], then nothing longer can. We try the longest first; if it fails, we fall back to lps[lps[k-1]-1], and so on.

fallback_visual.txt
VISUALIZING THE FALLBACK
 
Pattern: A A B A A A B
Positions:     [0] [1] [2] [3] [4] [5] [6]
               A   A   B   A   A   A   B
 
At i=5, trying to extend length=2 overlap:
Current overlap: pattern[0..1] = pattern[3..4] = "AA"
Try pattern[2]='B' vs pattern[5]='A': FAIL
 
Now we need a shorter valid prefix that could extend.
 
What's inside our overlap pattern[0..1] = "AA"?
lps[1] = 1 means pattern[0..0] = "A" is also a suffix of "AA".
 
So pattern[0..0] = "A" matches pattern[4..4] = "A"
(the suffix of our known-matching region)
 
Try pattern[1]='A' vs pattern[5]='A': SUCCESS!
length = 2, lps[5] = 2
 
The "A" at position 0 matched the "A" at position 4,
Now the "A" at position 1 matches the "A" at position 5.
So pattern[0..1] = "AA" matches pattern[4..5] = "AA".
 
This is a DIFFERENT "AA" overlap than before:
Before: positions 0-1 matching 3-4
After:  positions 0-1 matching 4-5

Complete KMP Implementation

Now let's see the complete KMP implementation with both LPS construction and pattern matching:

kmp_complete.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
def kmp_search(text: str, pattern: str) -> list[int]:
    """
    Complete KMP algorithm implementation.
    
    Finds all occurrences of pattern in text using the 
    Knuth-Morris-Pratt algorithm.
    
    Time Complexity: O(n + m) where n = len(text), m = len(pattern)
    Space Complexity: O(m) for the LPS array
    
    Args:
        text: The text to search in
        pattern: The pattern to search for
        
    Returns:
        List of starting indices where pattern occurs in text
    """
    n, m = len(text), len(pattern)
    
    # Edge cases
    if m == 0:
        return list(range(n + 1))  # Empty pattern matches at every position
    if n < m:
        return []  # Pattern longer than text
    
    # ========================================
    # PHASE 1: Build the LPS array - O(m)
    # ========================================
    lps = [0] * m
    length = 0  # Length of the previous longest prefix-suffix
    i = 1
    
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length > 0:
                length = lps[length - 1]  # Fallback
            else:
                lps[i] = 0
                i += 1
    
    # ========================================
    # PHASE 2: Search for pattern - O(n)
    # ========================================
    matches = []
    i = 0  # Index in text
    j = 0  # Index in pattern
    
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            
            if j == m:
                # Complete match found!
                matches.append(i - m)
                
                # Continue searching for overlapping matches
                j = lps[j - 1]
        else:
            if j > 0:
                j = lps[j - 1]  # Use LPS to skip
            else:
                i += 1  # Move to next text position
    
    return matches
 
 
# ========================================
# TESTING AND VERIFICATION
# ========================================
 
def verify_lps(pattern: str, lps: list[int]) -> bool:
    """Verify that an LPS array is correct (for testing)."""
    for i in range(len(pattern)):
        # lps[i] should be the longest proper prefix = suffix of pattern[0..i]
        k = lps[i]
        if k > i:
            return False  # lps[i] can't exceed i
        if k > 0:
            if pattern[0:k] != pattern[i-k+1:i+1]:
                return False  # The prefix-suffix must actually match
    return True
 
 
# Example usage
if __name__ == "__main__":
    text = "ABABABABCABAAB"
    pattern = "ABABC"
    
    print(f"Text: {text}")
    print(f"Pattern: {pattern}")
    print(f"Matches at positions: {kmp_search(text, pattern)}")

KMP Components Summary
Component	Lines	Complexity	Purpose
LPS Construction	30-42	O(m)	Preprocess pattern structure
Matching Loop	48-63	O(n)	Find all occurrences
Match Recording	57-59	O(1) each	Store match positions
Overlap Continuation	62	O(1)	Handle overlapping matches

Alternative Implementations

The KMP algorithm can be implemented in various languages. Here are optimized versions:

kmp.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def kmp_search(text: str, pattern: str) -> list[int]:
    """Memory-efficient KMP with generator option."""
    n, m = len(text), len(pattern)
    if m == 0 or n < m:
        return [] if n < m else list(range(n + 1))
    
    # Build LPS
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = lps[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        lps[i] = k
    
    # Search
    matches = []
    j = 0
    for i, char in enumerate(text):
        while j > 0 and char != pattern[j]:
            j = lps[j - 1]
        if char == pattern[j]:
            j += 1
        if j == m:
            matches.append(i - m + 1)
            j = lps[j - 1]
    
    return matches

Data Structures & AlgorithmsKMP Algorithm

KMP Algorithm — Failure Function & Matching

LevelIntermediate

Duration75 mins

TopicKMP Algorithm

5 / 5

Building the Failure Function

The Self-Referential Elegance

We've seen what the LPS array contains and how it enables efficient pattern matching. But how do we build the LPS array efficiently? The naive approach would be: for each position i, try all possible prefix lengths and check if they match the corresponding suffix. This would be O(m³) or O(m²) with optimization—far too slow for large patterns. The breakthrough insight is beautiful in its self-reference: we use the same pattern-matching technique to build the LPS array that we'll later use for text matching . The pattern becomes both the "text" and the "pattern" in a brilliant recursive construction. This is one of the most elegant algorithms in computer science—efficient, correct, and conceptually deep.

What You Will Learn

By the end of this page, you will understand the complete LPS construction algorithm, why it works, and how to implement it. You'll see the elegant recursion that makes O(m) possible and be able to trace the algorithm by hand.

The Naive Approach — Why It's Too Slow

Before appreciating the efficient algorithm, let's understand why the obvious approach fails. Naive Algorithm: def naive_lps(pattern): m = len(pattern) lps = [0] * m for i in range(1, m): # For each position i, find longest proper prefix = suffix for length in range(i, 0, -1): # Try longest first prefix = pattern[0:length] suffix = pattern[i-length+1:i+1] if prefix == suffix: lps[i] = length break return lps Complexity Analysis: Outer loop: m iterations Inner loop: up to i iterations (checking lengths from i down to 1) String comparison: up to i characters each Total: O(m³) in the worst case For a pattern of 100,000 characters, this is 10¹⁵ operations—completely impractical.

The Redundancy Problem

The naive algorithm repeatedly compares the same substrings. If we've determined that 'ABAB' has LPS of 2 ('AB' matches), why should we re-examine 'AB' when computing the next LPS value? This redundancy is exactly what KMP's construction algorithm eliminates.

The Key Insight — Building Incrementally

The efficient construction uses a powerful observation: If we know LPS[i-1], we can compute LPS[i] by trying to extend the previous overlap. Let's say LPS[i-1] = k. This means: pattern[0..k-1] = pattern[i-k..i-1] The first k characters equal the last k characters of pattern[0..i-1] Now we want LPS[i]. There are two cases: Case 1: pattern[k] == pattern[i] The overlap extends! We have: pattern[0..k] = pattern[i-k..i] LPS[i] = k + 1

extend_case.txt
EXTENDING AN OVERLAP
 
Previous state: pattern[0..i-1], LPS[i-1] = k
 
Pattern: ... [0] [1] ... [k-1] [k] ... [i-k] [i-k+1] ... [i-1] [i]
              └─── prefix (k chars) ───┘    └──── suffix (k chars) ────┘
                        ↑                           ↑
                    These are equal (LPS[i-1] = k)
 
Now checking if pattern[k] == pattern[i]:
 
Pattern: ... [0] [1] ... [k-1] [k] ... [i-k] [i-k+1] ... [i-1] [i]
                              ↑                               ↑
                        pattern[k]                       pattern[i]
 
If they're equal:
- pattern[0..k] = pattern[i-k..i]
- The k-length overlap becomes (k+1)-length
- LPS[i] = k + 1

Case 2: pattern[k] != pattern[i] The overlap doesn't extend. But we shouldn't give up—there might be a shorter overlap that we can extend. Here's the key: the next candidate length to try is LPS[k-1] . Why? Because LPS[k-1] is the longest proper prefix of pattern[0..k-1] that equals a suffix. And since pattern[0..k-1] equals a suffix of what we're building, this "nested" overlap might extend to include pattern[i].

The Recursive Insight

When extension fails, we "fall back" to LPS[k-1] and try again. This is the exact same fallback logic that happens during matching! We're matching the pattern against itself, using previously computed LPS values.

The Complete Algorithm

Here's the complete, efficient LPS construction algorithm:

lps_construction.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def compute_lps(pattern: str) -> list[int]:
    """
    Compute the LPS (Longest Proper Prefix which is also Suffix) array.
    
    Time Complexity: O(m) where m = len(pattern)
    Space Complexity: O(m) for the LPS array
    
    Args:
        pattern: The pattern string to preprocess
        
    Returns:
        LPS array where LPS[i] = length of longest proper prefix of 
        pattern[0..i] that is also a suffix of pattern[0..i]
    """
    m = len(pattern)
    
    if m == 0:
        return []
    
    lps = [0] * m  # LPS[0] is always 0 (no proper prefix for single char)
    
    # 'length' tracks the length of the current longest prefix-suffix
    # Think of it as: "I have matched 'length' characters of the prefix"
    length = 0
    
    # Start from index 1 (LPS[0] = 0 is given)
    i = 1
    
    while i < m:
        if pattern[i] == pattern[length]:
            # Extension successful!
            # The prefix pattern[0..length] matches suffix ending at i
            length += 1
            lps[i] = length
            i += 1
            
        else:
            # Extension failed
            if length > 0:
                # Fall back to the next candidate: LPS[length-1]
                # This is the "nested" overlap within our current overlap
                length = lps[length - 1]
                # NOTE: we do NOT increment i here - we retry with shorter length
                
            else:
                # length is 0, no prefix matches
                lps[i] = 0
                i += 1
    
    return lps

Key Points in the Algorithm: length variable: Tracks how many characters of prefix we've matched to suffix. Extension (line 30-33): When pattern[i] matches pattern[length], we've extended our prefix-suffix match. Fallback (line 38): When extension fails but length > 0, we use the LPS value at position length-1 to find the next candidate. Not incrementing i during fallback: This is crucial! We keep trying shorter overlaps at the same position i until we either find one that extends, or exhaust all possibilities (length becomes 0). Reset (lines 41-43): When length = 0 and we still mismatch, there's no prefix-suffix—LPS[i] = 0.

Detailed Trace Through Examples

Let's trace through the algorithm with several patterns to deeply understand how it works. Example 1: Pattern "ABCAB"

trace_abcab.txt
Pattern: A B C A B
Index:   0 1 2 3 4
 
Initialize: lps = [0, 0, 0, 0, 0], length = 0, i = 1
 
─────────────────────────────────────────────────────────
 
i = 1, length = 0:
Compare pattern[1]='B' with pattern[0]='A': NOT EQUAL
length = 0, so: lps[1] = 0, i++
→ lps = [0, 0, 0, 0, 0], length = 0, i = 2
 
─────────────────────────────────────────────────────────
 
i = 2, length = 0:
Compare pattern[2]='C' with pattern[0]='A': NOT EQUAL
length = 0, so: lps[2] = 0, i++
→ lps = [0, 0, 0, 0, 0], length = 0, i = 3
 
─────────────────────────────────────────────────────────
 
i = 3, length = 0:
Compare pattern[3]='A' with pattern[0]='A': EQUAL ✓
length++, lps[3] = 1, i++
→ lps = [0, 0, 0, 1, 0], length = 1, i = 4
 
─────────────────────────────────────────────────────────
 
i = 4, length = 1:
Compare pattern[4]='B' with pattern[1]='B': EQUAL ✓
length++, lps[4] = 2, i++
→ lps = [0, 0, 0, 1, 2], length = 2, i = 5
 
─────────────────────────────────────────────────────────
 
i = 5 = m, DONE!
 
FINAL: LPS = [0, 0, 0, 1, 2]

Example 2: Pattern "AABAAAB" (with fallbacks)

trace_aabaaab.txt
Pattern: A A B A A A B
Index:   0 1 2 3 4 5 6
 
Initialize: lps = [0, 0, 0, 0, 0, 0, 0], length = 0, i = 1
 
─────────────────────────────────────────────────────────
 
i = 1, length = 0:
Compare pattern[1]='A' with pattern[0]='A': EQUAL ✓
length = 1, lps[1] = 1, i = 2
→ lps = [0, 1, 0, 0, 0, 0, 0]
 
─────────────────────────────────────────────────────────
 
i = 2, length = 1:
Compare pattern[2]='B' with pattern[1]='A': NOT EQUAL
length > 0, so fallback: length = lps[0] = 0
(i stays at 2)
 
length = 0:
Compare pattern[2]='B' with pattern[0]='A': NOT EQUAL
length = 0, so: lps[2] = 0, i = 3
→ lps = [0, 1, 0, 0, 0, 0, 0]
 
─────────────────────────────────────────────────────────
 
i = 3, length = 0:
Compare pattern[3]='A' with pattern[0]='A': EQUAL ✓
length = 1, lps[3] = 1, i = 4
→ lps = [0, 1, 0, 1, 0, 0, 0]
 
─────────────────────────────────────────────────────────
 
i = 4, length = 1:
Compare pattern[4]='A' with pattern[1]='A': EQUAL ✓
length = 2, lps[4] = 2, i = 5
→ lps = [0, 1, 0, 1, 2, 0, 0]
 
─────────────────────────────────────────────────────────
 
i = 5, length = 2:
Compare pattern[5]='A' with pattern[2]='B': NOT EQUAL
length > 0, so fallback: length = lps[1] = 1
(i stays at 5)
 
length = 1:
Compare pattern[5]='A' with pattern[1]='A': EQUAL ✓
length = 2, lps[5] = 2, i = 6
→ lps = [0, 1, 0, 1, 2, 2, 0]
 
─────────────────────────────────────────────────────────
 
i = 6, length = 2:
Compare pattern[6]='B' with pattern[2]='B': EQUAL ✓
length = 3, lps[6] = 3, i = 7
→ lps = [0, 1, 0, 1, 2, 2, 3]
 
─────────────────────────────────────────────────────────
 
i = 7 = m, DONE!
 
FINAL: LPS = [0, 1, 0, 1, 2, 2, 3]
 
NOTE: At i=5, we had a FALLBACK.
pattern[5..5] = "A" didn't extend the "AA" overlap (position 2 is 'B').
But after falling back, "A" DID extend the "A" overlap.
lps[5] = 2 means "AA" (prefix) matches "AA" (the last two A's at positions 4,5).

Watch the Fallback Carefully

At position 5, we tried to extend the 'AAB' prefix, failed, fell back to extending 'A', and succeeded. This is the power of the recursive fallback—it finds the best possible overlap without restarting from scratch.

Why the Fallback Logic Works

The fallback length = lps[length - 1] might seem magical. Let's prove it's correct. Claim: When we can't extend a length-k overlap to include pattern[i], the next candidate overlap to try is of length lps[k-1]. Proof: We have: pattern[0..k-1] = pattern[i-k..i-1] (our current k-length overlap) pattern[k] \neq pattern[i] (extension failed) We're looking for a shorter prefix that could extend. Suppose there's a length-j overlap (j < k) that can extend: pattern[0..j-1] = pattern[i-j..i-1] pattern[j] = pattern[i] (extension succeeds) Question: What are the valid candidates for j? Since pattern[0..j-1] must equal pattern[i-j..i-1], and we know pattern[0..k-1] = pattern[i-k..i-1], the substring pattern[i-j..i-1] is a suffix of both: A suffix of pattern[0..i-1] Therefore a suffix of pattern[0..k-1] (since last k chars are our known overlap) So pattern[0..j-1] must be both: A prefix of the pattern A suffix of pattern[0..k-1] (our previous overlap region) This is exactly the definition of "proper prefix of pattern[0..k-1] that is also a suffix"—which is what lps[k-1] measures!

The Largest Valid Candidate

lps[k-1] is the LONGEST prefix of pattern[0..k-1] that is also a suffix. If this can't extend to include pattern[i], then nothing longer can. We try the longest first; if it fails, we fall back to lps[lps[k-1]-1], and so on.

fallback_visual.txt
VISUALIZING THE FALLBACK
 
Pattern: A A B A A A B
Positions:     [0] [1] [2] [3] [4] [5] [6]
               A   A   B   A   A   A   B
 
At i=5, trying to extend length=2 overlap:
Current overlap: pattern[0..1] = pattern[3..4] = "AA"
Try pattern[2]='B' vs pattern[5]='A': FAIL
 
Now we need a shorter valid prefix that could extend.
 
What's inside our overlap pattern[0..1] = "AA"?
lps[1] = 1 means pattern[0..0] = "A" is also a suffix of "AA".
 
So pattern[0..0] = "A" matches pattern[4..4] = "A"
(the suffix of our known-matching region)
 
Try pattern[1]='A' vs pattern[5]='A': SUCCESS!
length = 2, lps[5] = 2
 
The "A" at position 0 matched the "A" at position 4,
Now the "A" at position 1 matches the "A" at position 5.
So pattern[0..1] = "AA" matches pattern[4..5] = "AA".
 
This is a DIFFERENT "AA" overlap than before:
Before: positions 0-1 matching 3-4
After:  positions 0-1 matching 4-5

Complete KMP Implementation

Now let's see the complete KMP implementation with both LPS construction and pattern matching:

kmp_complete.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
def kmp_search(text: str, pattern: str) -> list[int]:
    """
    Complete KMP algorithm implementation.
    
    Finds all occurrences of pattern in text using the 
    Knuth-Morris-Pratt algorithm.
    
    Time Complexity: O(n + m) where n = len(text), m = len(pattern)
    Space Complexity: O(m) for the LPS array
    
    Args:
        text: The text to search in
        pattern: The pattern to search for
        
    Returns:
        List of starting indices where pattern occurs in text
    """
    n, m = len(text), len(pattern)
    
    # Edge cases
    if m == 0:
        return list(range(n + 1))  # Empty pattern matches at every position
    if n < m:
        return []  # Pattern longer than text
    
    # ========================================
    # PHASE 1: Build the LPS array - O(m)
    # ========================================
    lps = [0] * m
    length = 0  # Length of the previous longest prefix-suffix
    i = 1
    
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length > 0:
                length = lps[length - 1]  # Fallback
            else:
                lps[i] = 0
                i += 1
    
    # ========================================
    # PHASE 2: Search for pattern - O(n)
    # ========================================
    matches = []
    i = 0  # Index in text
    j = 0  # Index in pattern
    
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            
            if j == m:
                # Complete match found!
                matches.append(i - m)
                
                # Continue searching for overlapping matches
                j = lps[j - 1]
        else:
            if j > 0:
                j = lps[j - 1]  # Use LPS to skip
            else:
                i += 1  # Move to next text position
    
    return matches
 
 
# ========================================
# TESTING AND VERIFICATION
# ========================================
 
def verify_lps(pattern: str, lps: list[int]) -> bool:
    """Verify that an LPS array is correct (for testing)."""
    for i in range(len(pattern)):
        # lps[i] should be the longest proper prefix = suffix of pattern[0..i]
        k = lps[i]
        if k > i:
            return False  # lps[i] can't exceed i
        if k > 0:
            if pattern[0:k] != pattern[i-k+1:i+1]:
                return False  # The prefix-suffix must actually match
    return True
 
 
# Example usage
if __name__ == "__main__":
    text = "ABABABABCABAAB"
    pattern = "ABABC"
    
    print(f"Text: {text}")
    print(f"Pattern: {pattern}")
    print(f"Matches at positions: {kmp_search(text, pattern)}")

KMP Components Summary
Component	Lines	Complexity	Purpose
LPS Construction	30-42	O(m)	Preprocess pattern structure
Matching Loop	48-63	O(n)	Find all occurrences
Match Recording	57-59	O(1) each	Store match positions
Overlap Continuation	62	O(1)	Handle overlapping matches

Alternative Implementations

The KMP algorithm can be implemented in various languages. Here are optimized versions:

kmp.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def kmp_search(text: str, pattern: str) -> list[int]:
    """Memory-efficient KMP with generator option."""
    n, m = len(text), len(pattern)
    if m == 0 or n < m:
        return [] if n < m else list(range(n + 1))
    
    # Build LPS
    lps = [0] * m
    k = 0
    for i in range(1, m):
        while k > 0 and pattern[i] != pattern[k]:
            k = lps[k - 1]
        if pattern[i] == pattern[k]:
            k += 1
        lps[i] = k
    
    # Search
    matches = []
    j = 0
    for i, char in enumerate(text):
        while j > 0 and char != pattern[j]:
            j = lps[j - 1]
        if char == pattern[j]:
            j += 1
        if j == m:
            matches.append(i - m + 1)
            j = lps[j - 1]
    
    return matches

Building the Failure Function

The Self-Referential Elegance

The Naive Approach — Why It's Too Slow

The Key Insight — Building Incrementally

The Complete Algorithm

Detailed Trace Through Examples

Why the Fallback Logic Works

Complete KMP Implementation

Alternative Implementations

There’s more to understand.

Building the Failure Function

The Self-Referential Elegance

The Naive Approach — Why It's Too Slow

The Key Insight — Building Incrementally

The Complete Algorithm

Detailed Trace Through Examples

Why the Fallback Logic Works

Complete KMP Implementation

Alternative Implementations

There’s more to understand.