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

Time Complexity: KMP Pattern Matching Algorithm

O(N + M)

Understanding Time Complexity

We want to understand how fast the KMP algorithm finds a pattern inside a text.

Specifically, how the time grows as the text and pattern get longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void computeLPSArray(char* pat, int M, int* lps) {
    int len = 0, i = 1;
    lps[0] = 0;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) len = lps[len - 1];
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void KMPSearch(char* pat, char* txt) {
    int M = strlen(pat);
    int N = strlen(txt);
    int lps[M];
    computeLPSArray(pat, M, lps);
    int i = 0, j = 0;
    while (i < N) {
        if (pat[j] == txt[i]) {
            i++; j++;
        }
        if (j == M) {
            j = lps[j - 1];
        } else if (i < N && pat[j] != txt[i]) {
            if (j != 0) j = lps[j - 1];
            else i++;
        }
    }
}
    

This code finds all occurrences of a pattern inside a text efficiently using the KMP algorithm.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loops that traverse the pattern and text arrays.
• How many times: Each character in the text and pattern is visited at most twice.

How Execution Grows With Input

As the text length (N) and pattern length (M) grow, the operations increase roughly in a straight line.

Input Size (N, M)	Approx. Operations
10, 3	About 20-30 operations
100, 10	About 200-300 operations
1000, 50	About 1000-1100 operations

Pattern observation: The work grows linearly with the size of text and pattern combined.

Final Time Complexity

Time Complexity: O(N + M)

This means the time to find the pattern grows in a straight line with the text and pattern sizes.

Common Mistake

[X] Wrong: "KMP takes quadratic time because of nested loops."

[OK] Correct: The loops do not restart fully; the algorithm smartly skips characters, so each is processed only a few times.

Interview Connect

Understanding KMP's time complexity shows you can analyze efficient algorithms that avoid repeated work, a key skill in problem solving.

Self-Check

"What if we used a naive pattern search instead of KMP? How would the time complexity change?"