KMP Pattern Matching Algorithm in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of KMP prefix table computation

What is the output of the prefix table (lps array) after running the KMP preprocessing on the pattern "ABABCABAB"?

DSA Java

public class KMP {
    public static int[] computeLPSArray(String pat) {
        int M = pat.length();
        int[] lps = new int[M];
        int len = 0;
        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 main(String[] args) {
        int[] lps = computeLPSArray("ABABCABAB");
        for (int val : lps) {
            System.out.print(val + " ");
        }
    }
}

A [0, 0, 1, 2, 3, 0, 1, 2, 3]

B [0, 1, 0, 1, 2, 3, 0, 1, 2]

C [0, 0, 1, 2, 0, 1, 2, 3, 4]

D [0, 0, 1, 1, 0, 1, 2, 3, 4]

💡 Hint

Remember the prefix table stores the length of the longest proper prefix which is also suffix for each prefix of the pattern.

The prefix table for pattern "ABABCABAB" is computed step-by-step, resulting in the array [0, 0, 1, 2, 0, 1, 2, 3, 4]. This array helps the KMP algorithm skip unnecessary comparisons.

❓ Predict Output

intermediate

KMP search output for pattern in text

What is the output of the following KMP search code when searching for pattern "ABABCABAB" in text "ABABDABABCABAB"?

DSA Java

public class KMP {
    public static int[] computeLPSArray(String pat) {
        int M = pat.length();
        int[] lps = new int[M];
        int len = 0;
        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;
        int j = 0;
        while (i < N) {
            if (pat.charAt(j) == txt.charAt(i)) {
                i++;
                j++;
            }
            if (j == M) {
                System.out.print((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) {
        KMPSearch("ABABCABAB", "ABABDABABCABAB");
    }
}

A 5

B 6 7

C 5 7

D 6

💡 Hint

The pattern appears once starting at index 5 in the text.

The pattern "ABABCABAB" occurs once in the text "ABABDABABCABAB" starting at index 5. The KMP algorithm prints the starting index of each match.

🔧 Debug

advanced

Identify the bug in KMP prefix table computation

What error will the following code produce when computing the prefix table for pattern "AAAA"?

DSA Java

public static int[] computeLPSArray(String pat) {
    int M = pat.length();
    int[] lps = new int[M];
    int len = 0;
    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;
}

A No error, returns [0,1,2,3]

B NullPointerException

C Infinite loop

D ArrayIndexOutOfBoundsException

💡 Hint

Check the loop condition and array indexing carefully.

The loop condition uses i <= M, but array indices go from 0 to M-1. Accessing pat.charAt(i) when i == M causes ArrayIndexOutOfBoundsException.

🧠 Conceptual

advanced

Understanding KMP algorithm efficiency

Why does the KMP algorithm run in O(N + M) time, where N is the length of the text and M is the length of the pattern?

A Because it sorts the pattern and text before searching

B Because it uses a prefix table to avoid re-examining characters in the text after a mismatch

C Because it compares every character of the pattern with every character of the text

D Because it uses recursion to divide the text into smaller parts

💡 Hint

Think about how the prefix table helps skip unnecessary comparisons.

KMP uses the prefix table (lps array) to know how many characters can be skipped after a mismatch, so it never moves backwards in the text, resulting in linear time complexity O(N + M).

🚀 Application

expert

Find all occurrences of pattern in text using KMP

Given the text "ABC ABCDAB ABCDABCDABDE" and pattern "ABCDABD", what are the starting indices of all occurrences of the pattern in the text using KMP?

DSA Java

public class KMP {
    public static int[] computeLPSArray(String pat) {
        int M = pat.length();
        int[] lps = new int[M];
        int len = 0;
        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;
        int j = 0;
        while (i < N) {
            if (pat.charAt(j) == txt.charAt(i)) {
                i++;
                j++;
            }
            if (j == M) {
                System.out.print((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) {
        KMPSearch("ABCDABD", "ABC ABCDAB ABCDABCDABDE");
    }
}

A 4 11

B 4 15

C 4 11 15

D 11 15

💡 Hint

Check carefully where the pattern fully matches in the text.

The pattern "ABCDABD" appears twice in the text starting at indices 4 and 11. The KMP algorithm prints these starting indices.

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