KMP Pattern Matching Algorithm in DSA Python - Time & Space Complexity

Time Complexity: KMP Pattern Matching Algorithm

O(n + m)

Understanding Time Complexity

We want to understand how the KMP algorithm's running time changes as the text and pattern sizes grow.

Specifically, how fast can it find a pattern inside a text?

Scenario Under Consideration

Analyze the time complexity of the following KMP pattern matching code.

def compute_lps(pattern):
    lps = [0] * len(pattern)
    length = 0
    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
  

This code builds the longest prefix suffix (LPS) array for the pattern, which helps skip unnecessary comparisons.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that processes each character of the pattern once.
• How many times: At most twice per character, but overall linear to pattern length.

How Execution Grows With Input

The number of operations grows roughly in a straight line with the pattern length.

Input Size (pattern length)	Approx. Operations
10	About 20
100	About 200
1000	About 2000

Pattern observation: Doubling the pattern size roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n + m)

This means the algorithm checks each character of the text and pattern at most once, making it very efficient.

Common Mistake

[X] Wrong: "The KMP algorithm has a nested loop causing O(n*m) time like naive search."

[OK] Correct: KMP cleverly uses the LPS array to avoid rechecking characters, so it never goes back in the text, keeping time linear.

Interview Connect

Understanding KMP's time complexity shows you can analyze efficient algorithms that improve over simple methods, a key skill in interviews.

Self-Check

"What if the pattern is much longer than the text? How would that affect the time complexity?"