KMP Pattern Matching Algorithm in DSA Java - Build from Scratch

KMP Pattern Matching Algorithm

📖 Scenario: Imagine you are building a text search tool that quickly finds a smaller word or phrase inside a large document. This tool uses a smart method called the KMP algorithm to speed up the search by remembering where to continue checking after a mismatch.

🎯 Goal: You will build the KMP pattern matching algorithm in Java. This algorithm finds all starting positions where a given pattern appears in a text efficiently.

📋 What You'll Learn

Create an integer array called lps to store longest prefix suffix values

Write a method computeLPSArray that fills the lps array for the pattern

Write a method KMPSearch that uses the lps array to find all pattern occurrences in the text

Print all starting indices where the pattern is found in the text

💡 Why This Matters

🌍 Real World

Text editors, search engines, and DNA sequence analysis use pattern matching algorithms like KMP to quickly find patterns inside large texts or data.

💼 Career

Understanding KMP helps in software development roles that involve text processing, search optimization, and algorithm design.

1

Create the text and pattern strings

Create two string variables called text and pattern with these exact values: "ABABDABACDABABCABAB" for text and "ABABCABAB" for pattern.

DSA Java

// Your code here

Hint

Use String type and assign the exact text and pattern values.

2

Create the LPS array and the computeLPSArray method

Add an integer array called lps with length equal to pattern.length(). Then write a method called computeLPSArray that takes pattern and lps as parameters and fills lps with longest prefix suffix values for the pattern.

DSA Java

public class KMP {
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int[] lps = new int[pattern.length()];
        // Write computeLPSArray method below
    }

    // Your code here
}

Hint

The computeLPSArray method uses two pointers to fill the lps array by comparing characters in the pattern.

3

Write the KMPSearch method to find pattern occurrences

Write a method called KMPSearch that takes pattern, text, and lps as parameters. Use two indices i for text and j for pattern to find all starting indices where the pattern appears in the text. Store these indices in a list called result.

DSA Java

public class KMP {
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int[] lps = new int[pattern.length()];
        computeLPSArray(pattern, lps);
        // Call KMPSearch method below
    }

    public static void computeLPSArray(String pattern, int[] lps) {
        int length = 0;
        int i = 1;
        lps[0] = 0;
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }

    // Your code here
}

Hint

The KMPSearch method uses two pointers to scan the text and pattern, adding start indices to result when matches are found.

4

Print all starting indices where the pattern is found

In the main method, after calling KMPSearch, print the list result to display all starting indices where the pattern appears in the text.

DSA Java

import java.util.ArrayList;
import java.util.List;

public class KMP {
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        int[] lps = new int[pattern.length()];
        computeLPSArray(pattern, lps);
        List result = KMPSearch(pattern, text, lps);
        // Print the result list below
    }

    public static void computeLPSArray(String pattern, int[] lps) {
        int length = 0;
        int i = 1;
        lps[0] = 0;
        while (i  KMPSearch(String pattern, String text, int[] lps) {
        List result = new ArrayList();
        int i = 0; // index for text
        int j = 0; // index for pattern
        while (i < text.length()) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            if (j == pattern.length()) {
                result.add(i - j);
                j = lps[j - 1];
            } else if (i < text.length() && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return result;
    }

    // Your code here
}

Hint

Use System.out.println(result); to print the list of 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