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 work grows as the text and pattern get longer.

Scenario Under Consideration

Analyze the time complexity of the following KMP code snippet.

void computeLPSArray(string 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(string pat, string txt) {
    int M = pat.length(), N = txt.length();
    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 builds a helper array and then searches the pattern in the text efficiently.

Identify Repeating Operations

Look for loops and repeated steps.

• Primary operation: The while loops in computeLPSArray and KMPSearch that scan the pattern and text.
• How many times: Each loop runs at most once per character in pattern or text, no backtracking over characters.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
Pattern M=10, Text N=10	About 20 steps
Pattern M=100, Text N=100	About 200 steps
Pattern M=1000, Text N=1000	About 2000 steps

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

Final Time Complexity

Time Complexity: O(N + M)

This means the algorithm checks each character in the text and pattern only once, making it very efficient.

Common Mistake

[X] Wrong: "KMP is slower because it uses extra loops and backtracking."

[OK] Correct: The extra steps actually avoid repeating work, so the total steps stay linear, not quadratic.

Interview Connect

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

Self-Check

"What if the pattern was very long but the text was very short? How would the time complexity change?"

Practice

1. What is the main purpose of the KMP (Knuth-Morris-Pratt) algorithm in pattern matching?

easy

A. To find occurrences of a pattern in a text efficiently without rechecking characters

B. To sort the characters of the pattern alphabetically

C. To reverse the text before searching

D. To count the number of vowels in the text

Solution

1. Step 1: Understand KMP's goal

   KMP algorithm is designed to search for a pattern inside a text efficiently.

2. Step 2: Identify how it works

   It avoids rechecking characters by using a prefix table to skip unnecessary comparisons.

3. Final Answer:

   To find occurrences of a pattern in a text efficiently without rechecking characters -> Option A

4. Quick Check:

   KMP purpose = efficient pattern search [OK]

Hint: KMP skips repeated checks using prefix info [OK]

Common Mistakes:

• Thinking KMP sorts or modifies the text
• Confusing KMP with simple substring search
• Assuming KMP counts characters or vowels

2. Which of the following is the correct way to declare the prefix (lps) array in C++ for KMP algorithm?

easy

A. int lps[pattern_length];

B. int* lps = new int[pattern_length];

C. int lps = new int[pattern_length];

D. int lps[] = pattern_length;

Solution

1. Step 1: Understand dynamic array allocation in C++

   To create an array dynamically, use pointer with new keyword: int* lps = new int[size];

2. Step 2: Check options

   int* lps = new int[pattern_length]; correctly uses pointer and new to allocate array of given length.

3. Final Answer:

   int* lps = new int[pattern_length]; -> Option B

4. Quick Check:

   Dynamic array = int* lps = new int[size]; [OK]

Hint: Use int* with new[] for dynamic arrays in C++ [OK]

Common Mistakes:

• Using int lps = new int[] (wrong type)
• Declaring fixed size without initialization
• Incorrect array syntax like int lps[] = size

3. What will be the output of the following code snippet that uses KMP to find pattern occurrences?

std::string text = "ababcabcabababd";
std::string pattern = "ababd";
std::vector<int> result = kmpSearch(text, pattern);
for(int pos : result) std::cout << pos << " ";

Assuming kmpSearch returns all starting indices of pattern in text.

medium

A. 10

B. 0 5 10

C. 5 10

D. No output

Solution

1. Step 1: Identify pattern occurrences in text

   Check where "ababd" appears in "ababcabcabababd". It appears starting at index 10 only.

2. Step 2: Confirm output format

   kmpSearch returns vector of indices; printing them separated by space outputs "10 ".

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Pattern found at index 10 only [OK]

Hint: Scan text for exact pattern start index [OK]

Common Mistakes:

• Assuming multiple matches without checking text
• Confusing substring indices
• Printing no output if pattern not found

4. Consider this buggy code snippet for computing the LPS array in KMP:

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

What is the bug and how to fix it?

medium

A. Replace while with for loop

B. Initialize len to 1 instead of 0

C. Remove else block completely

D. Change len = lps[len]; to len = lps[len - 1];

Solution

1. Step 1: Identify incorrect index in LPS update

   When mismatch occurs and len != 0, len should be updated to lps[len-1], not lps[len].

2. Step 2: Correct the assignment

   Change len = lps[len]; to len = lps[len - 1]; to avoid out-of-bound and logical error.

3. Final Answer:

   Change len = lps[len]; to len = lps[len - 1]; -> Option D

4. Quick Check:

   LPS update uses len-1 index [OK]

Hint: Use len-1 index when updating len in LPS [OK]

Common Mistakes:

• Using len index directly causes wrong LPS values
• Changing loop type unnecessarily
• Removing else block breaks logic

5. Given a text and multiple patterns, which approach best uses KMP to find all patterns efficiently?

hard

A. Run KMP separately for each pattern on the text

B. Concatenate all patterns and run KMP once

C. Build a trie of patterns and run Aho-Corasick algorithm

D. Use KMP only on the longest pattern

Solution

1. Step 1: Understand KMP's limitation

   KMP efficiently finds one pattern in text but running it repeatedly for many patterns is inefficient.

2. Step 2: Identify better multi-pattern method

   Building a trie and using Aho-Corasick algorithm finds all patterns simultaneously efficiently.

3. Final Answer:

   Build a trie of patterns and run Aho-Corasick algorithm -> Option C

4. Quick Check:

   Multi-pattern search = Aho-Corasick [OK]

Hint: Use Aho-Corasick for multiple patterns [OK]

Common Mistakes:

• Running KMP repeatedly wastes time
• Concatenating patterns confuses matching
• Ignoring specialized multi-pattern algorithms