KMP Algorithm - Learning Module

Loading content...

0/276

Time Complexity: O(n + m)

The Guarantee That Matters

The KMP algorithm's claim to fame is its O(n + m) time complexity—linear in both the text length n and the pattern length m. This guarantee is profound because it means:

No input can cause slowdown: Unlike naive O(n×m) matching, adversarial inputs can't trigger pathological behavior.
Predictable performance: Processing time scales linearly with input size, essential for real-time systems.
Separable phases: O(m) preprocessing + O(n) matching means preprocessing is "free" when searching multiple texts.

But why is KMP O(n + m)? The answer isn't immediately obvious—the algorithm has loops within loops, fallback cascades, and pointer movements that seem potentially expensive. Let's prove this bound rigorously.

What You Will Learn

By the end of this page, you will understand the amortized analysis that proves KMP's O(n+m) complexity, see why the potential function argument works, and gain intuition for why no pathological input exists.

Breaking Down the Algorithm's Structure

The KMP algorithm has two distinct phases:

Phase 1: Preprocessing (Build LPS Array)

Input: Pattern of length m
Output: LPS array of length m
Goal: Compute LPS[i] for all 0 ≤ i < m

Phase 2: Matching (Search for Pattern in Text)

Input: Text of length n, Pattern of length m, LPS array
Output: All starting positions of pattern in text
Goal: Find all occurrences

We'll prove each phase has linear complexity separately.

kmp_structure.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
def kmp_search(text: str, pattern: str) -> list[int]:
    """
    Complete KMP algorithm with both phases.
    """
    n, m = len(text), len(pattern)
    
    if m == 0:
        return list(range(n + 1))  # Empty pattern matches everywhere
    if n < m:
        return []  # Pattern longer than text
    
    # ========================================
    # Phase 1: Build LPS array - O(m)
    # ========================================
    lps = [0] * m
    length = 0  # Length of 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 in text - O(n)
    # ========================================
    matches = []
    j = 0  # Index in pattern
    i = 0  # Index in text
    
    while i < n:
        if text[i] == pattern[j]:
            i += 1
            j += 1
            if j == m:
                matches.append(i - m)
                j = lps[j - 1]
        else:
            if j > 0:
                j = lps[j - 1]  # Fallback
            else:
                i += 1
    
    return matches

Algorithm Operations Summary
Operation	Phase	Frequency
Pattern character comparison	Both	Varies (to be analyzed)
i++ (text/pattern pointer advance)	Both	At most n+m total
j/length = lps[...] (fallback)	Both	Varies (to be analyzed)
LPS array write	Preprocessing	Exactly m times
Match recording	Matching	At most n-m+1 times

Preprocessing Complexity: O(m)

The LPS array construction has a loop with two possible branches:

Match: pattern[i] == pattern[length] → increment both, move forward
Mismatch with length > 0: fallback length = lps[length-1]
Mismatch with length = 0: just move i forward

The concern is branch 2—the fallback. Could we spiral into many fallbacks per index i?

The Amortized Argument:

Define a potential function Φ = length (the current value of the length variable).

Initially: Φ = 0
Finally: Φ ≥ 0 (length is never negative)

Analyzing each operation:

Match (increment length): Φ increases by 1. This happens at most m-1 times (can't exceed m-1 matches as i goes from 1 to m-1).
Fallback (length = lps[length-1]): Φ decreases. Since lps[length-1] < length always, each fallback reduces Φ by at least 1.
Mismatch with length=0: Φ stays at 0, i advances.

The Key Insight

Total increases to Φ ≤ m-1. Total decreases can't exceed total increases (since Φ ≥ 0 always). Therefore, total fallbacks ≤ m-1. Combined with i advancing m-1 times, total iterations ≤ 2(m-1) = O(m).

Detailed Proof:

Let's count operations precisely:

i++ happens exactly m-1 times (i goes from 1 to m-1)
Each i++ is accompanied by either:
- A match (length++), OR
- A final mismatch after 0+ fallbacks when length=0
Each fallback decreases length by at least 1
Total fallbacks ≤ total length increases (since length ≥ 0)
Total length increases ≤ m-1 (bounded by i advances)
Therefore: total fallbacks ≤ m-1

Total operations:

Comparisons: at most m-1 (one significant comparison per i advance)
Fallbacks: at most m-1
i advances: exactly m-1

Total: O(m)

preprocessing_trace.txt
Pattern: AABAAB (m = 6)
 
Trace LPS construction:
 
i=1: pattern[1]='A' vs pattern[0]='A' ✓
     length = 1, lps[1] = 1
     Φ = 1, comparisons = 1
 
i=2: pattern[2]='B' vs pattern[1]='A' ✗
     length > 0, so length = lps[0] = 0
     Φ = 0 (fallback, -1)
     
     pattern[2]='B' vs pattern[0]='A' ✗
     length = 0, so lps[2] = 0, i++
     Φ = 0, comparisons = 3
 
i=3: pattern[3]='A' vs pattern[0]='A' ✓
     length = 1, lps[3] = 1
     Φ = 1, comparisons = 4
 
i=4: pattern[4]='A' vs pattern[1]='A' ✓
     length = 2, lps[4] = 2
     Φ = 2, comparisons = 5
 
i=5: pattern[5]='B' vs pattern[2]='B' ✓
     length = 3, lps[5] = 3
     Φ = 3, comparisons = 6
 
Final LPS = [0, 1, 0, 1, 2, 3]
 
STATISTICS:
- Total comparisons: 6
- Total fallbacks: 1
- Total: 7 operations for m = 6
- Ratio: 1.17 (well under the 2m bound)

Matching Complexity: O(n)

The matching phase uses the same analysis approach. Define:

i = text pointer (starts at 0, ends at n)
j = pattern pointer (oscillates between 0 and m)
Potential Φ = j

Operations in the matching loop:

Match (i++, j++): Both pointers advance. Φ increases by 1.
Full match (j == m): j = lps[m-1]. Φ might decrease significantly, but this is fine—we earned those increases.
Mismatch with j > 0: j = lps[j-1]. Φ decreases.
Mismatch with j = 0: i++. Φ stays at 0.

The Bound:

The text pointer i advances exactly n times total (from 0 to n)
Each i advance is accompanied by a match (j++) OR is a "restart" when j=0
Total j increases ≤ n (one per text character, at most)
Total j decreases ≤ total j increases (since j ≥ 0)
Therefore total fallback operations ≤ n

Total operations in matching phase:

Text comparisons: ≤ 2n (each i advance might be paired with one fallback cascade, but total fallbacks ≤ n)
Pointer operations: O(n)

Total: O(n)

The Same Technique Works

Notice the identical structure: we bound decreases by increases, and increases are bounded by natural iteration limits. This potential function technique (also called amortized analysis) is powerful for analyzing algorithms with variable-cost iterations.

Matching Phase Operation Bounds
Operation	Bound	Reasoning
i increments	Exactly n	Text pointer visits each position once
j increments	At most n	One per character match
j decrements (fallbacks)	At most n	Can't exceed total increments
Match comparisons	At most 2n	Bounded by i advances + fallbacks

Combined Complexity: O(n + m)

Putting both phases together:

Total Time Complexity:

Preprocessing: O(m)
Matching: O(n)
Combined: O(n + m)

This is optimal for any algorithm that must:

Read the entire pattern (Ω(m) lower bound)
Potentially read the entire text (Ω(n) lower bound)

Space Complexity:

LPS array: O(m)
Pattern storage: O(m) (if not passed by reference)
Text storage: O(n) (if not streaming)
Other variables: O(1)

Total space: O(m) beyond input storage, since the LPS array is the only additional data structure.

Time Complexity Summary

•Preprocessing: O(m)
•Matching: O(n)
•Total: O(n + m)
•Worst case = Average case = Best case

Space Complexity Summary

•LPS Array: O(m)
•Pointers/counters: O(1)
•Total auxiliary: O(m)
•Can stream text: O(1) text space

No Worst Case Degradation

Unlike many algorithms where average case differs from worst case, KMP has the SAME complexity in all cases: O(n+m). There's no input that can trigger worse behavior. This makes KMP ideal for security-sensitive applications where attackers might craft malicious inputs.

Comparison with Naive Algorithm

Let's quantify the improvement KMP provides over the naive algorithm:

Naive Algorithm:

Time: O(n × m) worst case, O(n) best case
Space: O(1)
Worst case trigger: Repetitive patterns in repetitive text

KMP Algorithm:

Time: O(n + m) always
Space: O(m) for LPS array
No worst case trigger exists

Concrete Comparison: Finding 'AAAAAAB' in Text of All A's
Text Length n	Pattern Length m	Naive (worst)	KMP (always)	Speedup
1,000	100	100,000	1,100	~91×
10,000	100	1,000,000	10,100	~99×
100,000	100	10,000,000	100,100	~100×
1,000,000	1,000	1,000,000,000	1,001,000	~999×
10,000,000	10,000	100,000,000,000	10,010,000	~9,999×

Real-World Impact:

For a genome sequence search (n = 3 billion, m = 1,000):

Naive worst case: ~3 quadrillion comparisons (3 × 10¹⁵)
KMP: ~3 billion comparisons (3 × 10⁹)
Difference: 1 million× faster

At 10 billion comparisons per second:

Naive: ~3.5 days (worst case)
KMP: ~0.3 seconds

Constant Factors Matter Too

For small inputs, KMP's preprocessing overhead (building LPS array) might make it slower than naive. The crossover point is typically around m ≈ 5-10 characters. Below that, naive's O(1) setup often wins despite worse complexity.

Visual Proof of Linear Complexity

Let's visualize why the text pointer never backtracks and why total operations are bounded.

Key Visualization: The Text Pointer Only Advances

visual_proof.txt
Pattern: ABABAC (m=6, LPS = [0, 0, 1, 2, 3, 0])
Text:    ABABABABABAC (n=12)
 
Each row shows: (text pointer i, pattern pointer j)
The text pointer NEVER decreases.
 
i: 0  1  2  3  4  5  6  7  8  9  10 11 12
   │  │  │  │  │  │  │  │  │  │  │  │  │
j: 0→1→2→3→4→5│→3→4→5│→3→4→5→6 (match!)
              ↓      ↓
            mismatch mismatch
            fallback fallback
            j=3      j=3
 
PATTERN POINTER j OVER TIME:
Operation #:  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
j value:      1  2  3  4  5  3  4  5  3  4  5  6  -  -  -  -
              ↑  ↑  ↑  ↑  ↑  ↓  ↑  ↑  ↓  ↑  ↑  ↑
              +  +  +  +  +  -  +  +  -  +  +  +
 
Increases (+): 12
Decreases (-): 2  
Net j movement: 10 (ends at 6 from 0)
 
TEXT POINTER i OVER TIME:
i advances on: matches + restarts when j=0
i value:      0→1→2→3→4→5→5→6→7→7→8→9→10→11→12
                         ↑     ↑
                    stayed  stayed (during fallback)
 
i strictly advances or stays: NEVER DECREASES
 
TOTAL COMPARISONS: 16 (well under 2n+m = 30)

Why This Proves O(n):

The text pointer i advances to n, taking n steps
Each step either:
- Increments j (bounded by total j increments)
- Or occurs when j = 0
Total j increments ≤ n (one per text position at most)
Total j decrements ≤ n (bounded by increments)
Therefore total work ≤ 2n = O(n)

The Visual Invariant

Picture a graph with iteration number on x-axis and j value on y-axis. It goes up and down, but: (1) it starts at 0, (2) it ends at 0-m, (3) each up step costs one text comparison. Total up steps ≤ n, total down steps ≤ up steps, so area under curve = O(n).

Lower Bound — Is O(n + m) Optimal?

Is O(n + m) the best possible? For any algorithm that solves the pattern matching problem, can we prove a lower bound?

Theorem: Any algorithm that finds all occurrences of a pattern in a text requires Ω(n + m) comparisons in the worst case.

Proof Sketch:

Reading the pattern: To know what to search for, we must examine each of the m pattern characters at least once. Lower bound: Ω(m).
Reading the text: Consider the text where every position could potentially be a match start (e.g., text = pattern repeated with modifications). We must examine each of the n text characters. Lower bound: Ω(n).
Combined lower bound: Ω(n + m)

Conclusion: KMP is asymptotically optimal. No comparison-based algorithm can beat O(n + m).

Beyond Comparisons

This lower bound applies to comparison-based algorithms. Specialized hardware (SIMD) or preprocessing (suffix arrays, FM-indices) can achieve faster PRACTICAL performance for specific use cases, but can't beat O(n+m) asymptotically in the general comparison model.

String Matching Algorithm Comparison
Algorithm	Preprocessing	Matching	Total	Optimal?
Naive	O(1)	O(nm) worst	O(nm)	No
KMP	O(m)	O(n)	O(n+m)	Yes
Rabin-Karp	O(m)	O(n) avg, O(nm) worst	O(n+m) avg	Avg yes, worst no
Boyer-Moore	O(m + \|Σ\|)	O(n/m) best, O(nm) worst	O(n+m) typical	Practical often better
Z-Algorithm	O(m)	O(n)	O(n+m)	Yes

Summary: The O(n + m) Guarantee

We've rigorously analyzed the time complexity of the KMP algorithm. Let's consolidate our understanding:

Key Takeaways

•Preprocessing is O(m) — the potential function argument shows fallbacks can't exceed advances.
•Matching is O(n) — the text pointer never retreats; total pattern pointer movement is bounded.
•Combined: O(n + m) — two independent linear phases.
•Space is O(m) — only the LPS array needs storage beyond input.
•No worst case exists — every input triggers O(n + m), making KMP reliable for all scenarios.
•This is optimal — Ω(n + m) lower bound shows no comparison-based algorithm can do better.

What's next:

We've analyzed KMP's complexity but haven't yet seen the LPS construction algorithm in detail. The final page covers this elegantly recursive algorithm—showing how pattern-matching-against-itself yields the LPS array in O(m) time—completing our KMP mastery.

Page Complete

You now understand why KMP achieves O(n + m) time complexity, can prove this bound using amortized analysis, understand the space requirements, and know that this is asymptotically optimal. The complexity guarantee is what makes KMP a cornerstone of string algorithms.