KMP Pattern Matching Algorithm in DSA Java

Mental Model

KMP finds a pattern in a text by skipping unnecessary checks using a precomputed table.

Analogy: Imagine searching for a word in a book. Instead of going back to the start after a mismatch, you remember how much matched and jump ahead to avoid rechecking letters.

Text:  A B C D A B C D A B C D
Pattern:       A B C D
          ↑

Dry Run Walkthrough

Input: text: "ABABDABACDABABCABAB", pattern: "ABABCABAB"

Goal: Find all starting indices where pattern appears in text efficiently.

Step 1: Build longest prefix suffix (LPS) array for pattern

Pattern: A B A B C A B A B
LPS:     0 0 1 2 0 1 2 3 4

Why: LPS helps know how far to jump on mismatch without rechecking matched chars

Step 2: Start matching pattern at text index 0

Text: [A B A B D A B A C D A B A B C A B A B]
Pattern: [A B A B C A B A B]
Match indices: 0 to 3 matched

Why: We matched first 4 chars, next char mismatch at text index 4

Step 3: Mismatch at pattern index 4, use LPS to shift pattern index to 2

Pattern index moves from 4 to 2 using LPS
Text index stays at 4

Why: Avoid rechecking first 2 chars, jump pattern index to 2

Step 4: Continue matching from pattern index 2 and text index 4

Match fails at text index 4 and pattern index 2, move text index to 5

Why: Mismatch after shift, move text forward to try next match

Step 5: Continue matching pattern from start at text index 5

Match found from text index 10 to 18

Why: Full pattern matched, record index 10

Result:

Pattern found at indices: 10

Annotated Code

DSA Java

public class KMP {
    public static int[] computeLPSArray(String pat) {
        int M = pat.length();
        int[] lps = new int[M];
        int len = 0; // length of the previous longest prefix suffix
        int i = 1;
        while (i < M) {
            if (pat.charAt(i) == pat.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    public static void KMPSearch(String pat, String txt) {
        int M = pat.length();
        int N = txt.length();
        int[] lps = computeLPSArray(pat);
        int i = 0; // index for txt
        int j = 0; // index for pat
        while (i < N) {
            if (pat.charAt(j) == txt.charAt(i)) {
                i++;
                j++;
            }
            if (j == M) {
                System.out.println("Pattern found at index " + (i - j));
                j = lps[j - 1];
            } else if (i < N && pat.charAt(j) != txt.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
    }

    public static void main(String[] args) {
        String txt = "ABABDABACDABABCABAB";
        String pat = "ABABCABAB";
        KMPSearch(pat, txt);
    }
}

while (i < M) { if (pat.charAt(i) == pat.charAt(len)) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } }

Build LPS array to know how far to jump on mismatch

while (i < N) { if (pat.charAt(j) == txt.charAt(i)) { i++; j++; }

Advance both indices when characters match

if (j == M) { System.out.println("Pattern found at index " + (i - j)); j = lps[j - 1]; }

Pattern fully matched, record index and reset j using LPS

else if (i < N && pat.charAt(j) != txt.charAt(i)) { if (j != 0) { j = lps[j - 1]; } else { i++; } }

On mismatch, use LPS to avoid rechecking matched prefix or move text index

Output

Pattern found at index 10

Complexity Analysis

Time: O(n + m) because we scan the text and pattern once each using LPS to skip comparisons

Space: O(m) for the LPS array storing longest prefix suffix values for the pattern

vs Alternative: Naive search is O(n*m) because it rechecks characters after mismatch; KMP improves by skipping redundant checks

Edge Cases

Empty pattern

No matches found, function completes without printing

DSA Java

int M = pat.length();

Pattern longer than text

No matches found, loop exits immediately

DSA Java

while (i < N)

Pattern equals text

Pattern found at index 0

DSA Java

if (j == M)

When to Use This Pattern

When you need to find a pattern inside a text efficiently and want to avoid rechecking characters after mismatch, use KMP pattern matching.

Common Mistakes

Mistake: Not building the LPS array correctly, causing wrong jumps and missed matches.
Fix: Carefully update LPS using previous longest prefix suffix values and only advance index when characters match.

Mistake: Resetting pattern index j to zero on mismatch instead of using LPS array.
Fix: Use j = lps[j-1] to jump to the correct prefix position instead of restarting from zero.

Summary

Finds all occurrences of a pattern in a text efficiently by precomputing a jump table.

Use when you want fast pattern search without rechecking matched characters after mismatch.

The key is the LPS array that tells how far to jump in the pattern on mismatch.

Practice

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

easy

A. To count the number of vowels in a string

B. To sort characters in a string alphabetically

C. To reverse a string in linear time

D. To efficiently find occurrences of a pattern within a text

Solution

1. Step 1: Understand KMP's goal

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

2. Step 2: Compare with other options

   Sorting, reversing, or counting vowels are unrelated to pattern searching.

3. Final Answer:

   To efficiently find occurrences of a pattern within a text -> Option D

4. Quick Check:

   KMP = Pattern Searching [OK]

Hint: KMP is about fast pattern search, not string modification [OK]

Common Mistakes:

• Confusing KMP with sorting algorithms
• Thinking KMP reverses strings
• Assuming KMP counts characters

2. Which of the following is the correct way to initialize the prefix array (lps) in the KMP algorithm in Java?

easy

A. int[] lps = new int[pattern.length()];

B. int lps[] = new int[pattern.length() + 1];

C. int lps = new int[pattern.length()];

D. int[] lps = new int[pattern.length() - 1];

Solution

1. Step 1: Check array declaration syntax

   In Java, arrays are declared with type[], e.g., int[] lps.

2. Step 2: Check array size correctness

   Prefix array size equals pattern length, so new int[pattern.length()] is correct.

3. Final Answer:

   int[] lps = new int[pattern.length()]; -> Option A

4. Quick Check:

   Correct Java array init = int[] lps = new int[pattern.length()]; [OK]

Hint: Use int[] lps = new int[pattern.length()] for prefix array [OK]

Common Mistakes:

• Using incorrect array size (too big or too small)
• Wrong syntax like int lps instead of int[] lps
• Adding unnecessary +1 or -1 to length

3. What will be the output of the following Java code snippet using KMP to search pattern "ABABC" in text "ABABABCABABC"?

String text = "ABABABCABABC";
String pattern = "ABABC";
List<Integer> result = KMPSearch(pattern, text);
System.out.println(result);

Assume KMPSearch returns a list of starting indices where pattern is found.

medium

A. [1, 6]

B. [0, 5]

C. [2, 7]

D. [3, 8]

Solution

1. Step 1: Identify pattern occurrences in text

   Check text "ABABABCABABC" for "ABABC" starting indices: - At index 0: substring "ABABA" does not match fully - At index 2: substring "ABABC" matches fully - At index 5: substring "CABAB" does not match - At index 6: substring "ABABC" matches fully Actually, the pattern "ABABC" occurs at indices 2 and 7, but index 7 is out of range for the second match. Re-examining carefully: - At index 0: substring "ABABA" partial - At index 5: substring "CABAB" no - At index 6: substring "ABABC" matches - At index 7: substring "BABC" incomplete So matches at indices 2 and 6.

2. Step 2: Confirm no other matches

   Other indices do not match the full pattern exactly.

3. Final Answer:

   [2, 6] -> Option B

4. Quick Check:

   Pattern found at indices 2 and 6

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

Common Mistakes:

• Off-by-one errors in indexing
• Confusing partial matches as full matches
• Assuming matches start at 0 or 1 incorrectly

4. Consider this snippet of KMP prefix array (lps) computation in Java:

int len = 0;
int i = 1;
while (i < pattern.length()) {
  if (pattern.charAt(i) == pattern.charAt(len)) {
    len++;
    lps[i] = len;
    i++;
  } else {
    if (len != 0) {
      len = lps[len - 1];
    } else {
      lps[i] = 0;
      i++;
    }
  }
}

What is the bug in this code?

medium

A. Should increment i before assigning lps[i]

B. len should be reset to 0 instead of lps[len - 1]

C. No bug; code correctly computes lps array

D. Missing initialization of lps array before loop

Solution

1. Step 1: Analyze lps computation logic

   This code follows the standard KMP prefix array logic: - Increment len and assign lps[i] when chars match - Reset len using lps[len-1] when mismatch and len != 0 - Assign 0 and increment i when len == 0

2. Step 2: Verify no missing steps

   Initialization of lps array is assumed done before; loop logic is correct.

3. Final Answer:

   No bug; code correctly computes lps array -> Option C

4. Quick Check:

   Standard KMP lps logic = No bug; code correctly computes lps array [OK]

Hint: Standard KMP lps code is correct as given [OK]

Common Mistakes:

• Thinking i must increment before lps assignment
• Resetting len incorrectly to 0 instead of lps[len-1]
• Forgetting to initialize lps array before loop

5. Given the pattern "AABAACAABAA" and text "AABAACAABAABAABA", how many times will the KMP algorithm find the pattern in the text? Assume zero-based indexing and full matches only.

hard

A. 2

B. 1

C. 3

D. 4

Solution

1. Step 1: Search for pattern occurrences in text

   Check text "AABAACAABAABAABA" for pattern "AABAACAABAA": - At index 0: substring matches pattern fully - At index 7: substring "AABAACAABAA" matches fully - Other indices do not match fully

2. Step 2: Confirm matches

   Two full matches found at indices 0 and 7.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Pattern appears twice fully [OK]

Hint: Count only full pattern matches in text [OK]

Common Mistakes:

• Counting partial matches as full matches
• Missing the first match at index 0
• Assuming overlapping partial matches count