KMP Pattern Matching Algorithm in DSA Java - Deep Dive

Overview - KMP Pattern Matching Algorithm

What is it?

The KMP Pattern Matching Algorithm is a method to find a smaller string (pattern) inside a bigger string (text) efficiently. It avoids checking the same characters multiple times by remembering where to continue after a mismatch. This makes searching faster than checking every position from scratch. It is widely used in text processing and searching tasks.

Why it matters

Without KMP, searching for patterns in text can be slow, especially with large texts and complex patterns. This can make software like search engines, text editors, or DNA sequence analyzers inefficient. KMP speeds up these searches by reducing repeated work, saving time and computing power, which is crucial in real-world applications.

Where it fits

Before learning KMP, you should understand basic string operations and simple pattern searching methods like the naive approach. After KMP, you can explore other advanced pattern matching algorithms like Rabin-Karp or Boyer-Moore, and learn about automata theory or string preprocessing techniques.

Mental Model

Core Idea

KMP remembers how the pattern matches itself to skip unnecessary comparisons during searching.

Think of it like...

Imagine trying to find a word in a book by scanning each letter. Instead of starting over every time you find a mismatch, you remember parts of the word that matched and jump ahead, saving time.

Text:    a b c d a b c d a b c d
Pattern:       a b c d a b

Matching process:
Start comparing pattern from left to right.
On mismatch, use the pattern's own prefix info to shift pattern without re-checking matched characters.

Prefix Table (lps):
Index: 0 1 2 3 4 5
Value: 0 0 0 0 1 2

This table tells how far to jump back in pattern on mismatch.

Build-Up - 6 Steps

1

Foundation

Understanding Basic Pattern Searching

Concept: Learn how to find a pattern in text by checking each position one by one.

The naive approach checks every position in the text to see if the pattern starts there. For example, to find 'abc' in 'xabcd', check text[0..2], then text[1..3], and so on. This can be slow if the text and pattern are large.

Result

You can find if and where the pattern appears, but it may take a lot of time for big inputs.

Understanding the naive method shows why repeated checks waste time and sets the stage for smarter algorithms.

2

Foundation

What is the Longest Prefix Suffix (LPS) Array?

Concept: Learn to preprocess the pattern to find repeated parts inside it.

The LPS array stores, for each position in the pattern, the length of the longest prefix that is also a suffix up to that position. For example, for 'abab', the LPS array is [0,0,1,2]. This helps know where to restart matching after a mismatch.

Result

You get a table that tells how the pattern overlaps with itself.

Knowing the pattern's self-overlap helps avoid re-checking characters during search.

3

Intermediate

Building the LPS Array Step-by-Step

🤔Before reading on: do you think the LPS array can have values larger than half the pattern length? Commit to yes or no.

Concept: Learn the algorithm to create the LPS array efficiently in linear time.

Start with two pointers: length = 0 and i = 1. Compare pattern[i] with pattern[length]. If they match, increase length and set lps[i] = length, then move i forward. If not, if length is not zero, set length = lps[length-1], else lps[i] = 0 and move i forward. Repeat until the whole pattern is processed.

Result

You get the LPS array for any pattern in O(pattern length) time.

Understanding this process is key to KMP's efficiency and is often the hardest part to grasp.

4

Intermediate

Using LPS to Search Pattern in Text

🤔Before reading on: do you think the search restarts from the next character in text after a mismatch, or can it skip ahead? Commit to your answer.

Concept: Use the LPS array to skip unnecessary comparisons during the search phase.

Start comparing text and pattern from the beginning. On match, move both pointers forward. On mismatch, if pattern pointer is not zero, set it to lps[pattern pointer - 1] to skip ahead; else move text pointer forward. Repeat until pattern is found or text ends.

Result

The pattern is found in the text efficiently without re-checking matched characters.

This skipping mechanism is what makes KMP faster than naive search.

5

Advanced

Implementing KMP in Java with Comments

🤔Before reading on: do you think the code needs two separate loops for LPS and search, or can it be combined? Commit to your answer.

Concept: See a full Java implementation of KMP with clear comments explaining each step.

public class KMP { // Compute LPS array private int[] computeLPS(String pattern) { int length = 0; // length of previous longest prefix suffix int i = 1; int[] lps = new int[pattern.length()]; lps[0] = 0; // lps[0] is always 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++; } } } return lps; } // Search pattern in text public void search(String text, String pattern) { if (pattern == null || pattern.length() == 0) { System.out.println("Empty pattern"); return; } int[] lps = computeLPS(pattern); 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()) { System.out.println("Pattern found at index " + (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++; } } } } } // Example usage: // KMP kmp = new KMP(); // kmp.search("ababcababcababc", "ababc");

Result

The program prints all starting indices where the pattern appears in the text.

Seeing the full code clarifies how LPS and search phases work together in practice.

6

Expert

Why KMP is Linear Time and Its Limits

🤔Before reading on: do you think KMP always runs in linear time regardless of input? Commit to yes or no.

Concept: Understand why KMP guarantees O(n) time and where it might not be the best choice.

KMP uses the LPS array to avoid re-examining characters, ensuring each character in text and pattern is processed at most once, leading to O(n) time. However, KMP is not always fastest in practice for all patterns or alphabets. Algorithms like Boyer-Moore can skip more characters on average. Also, KMP requires preprocessing the pattern, which may not be efficient for one-time searches.

Result

You know when KMP is optimal and when other algorithms might be better.

Understanding KMP's time guarantees and tradeoffs helps choose the right algorithm for each problem.

Under the Hood

KMP works by preprocessing the pattern to build the LPS array, which encodes the longest proper prefix that is also a suffix for every prefix of the pattern. During the search, when a mismatch occurs, instead of restarting from the next character in the text, KMP uses the LPS array to shift the pattern to the right position, reusing previous match information. This avoids redundant comparisons and ensures each character is visited at most twice.

Why designed this way?

KMP was designed to improve over naive search by eliminating repeated comparisons caused by overlapping prefixes and suffixes in the pattern. Earlier methods restarted matching from scratch after mismatches, wasting time. KMP's insight was to use the pattern's internal structure to skip ahead efficiently. Alternatives like Rabin-Karp use hashing, but KMP is deterministic and does not rely on probabilistic checks.

Text:    a b c d a b c d a b c d
Pattern:       a b c d a b

LPS Array:
Index: 0 1 2 3 4 5
Value: 0 0 0 0 1 2

Search Flow:
[Match] -> Move forward
[Mismatch] -> Jump pattern index to lps[current-1]

Flowchart:
+-----------------+
| Start matching   |
+-----------------+
          |
          v
+-----------------+
| Characters match?|
+-----------------+
    | Yes       | No
    v           v
+---------+  +------------------+
| Move i,j|  | j != 0?          |
+---------+  +------------------+
              | Yes       | No
              v           v
        +---------+   +---------+
        | j = lps |   | i = i+1 |
        +---------+   +---------+

Myth Busters - 4 Common Misconceptions

Quick: Does KMP check every character in the text multiple times? Commit to yes or no.

Common Belief: KMP compares every character in the text multiple times, so it is not faster than naive search.

Reality: KMP ensures each character in the text is checked at most twice, making it run in linear time.

Why it matters: Believing KMP is slow can prevent learners from using it in performance-critical applications.

Quick: Is the LPS array the same as the pattern's prefix array? Commit to yes or no.

Common Belief: The LPS array is just the prefix of the pattern stored as numbers.

Reality: The LPS array stores the length of the longest proper prefix which is also a suffix for each prefix of the pattern, not just the prefix itself.

Why it matters: Misunderstanding LPS leads to incorrect implementation and failed pattern matching.

Quick: Does KMP work only for alphabets or any kind of data? Commit to yes or no.

Common Belief: KMP only works for text with alphabets like English letters.

Reality: KMP works for any sequence of elements, including numbers or bytes, as long as equality can be checked.

Why it matters: Limiting KMP to alphabets restricts its use in fields like bioinformatics or binary data processing.

Quick: Can KMP be used without preprocessing the pattern? Commit to yes or no.

Common Belief: You can run KMP search without building the LPS array first.

Reality: Preprocessing the pattern to build the LPS array is essential for KMP's efficiency; skipping it makes KMP no better than naive search.

Why it matters: Skipping preprocessing wastes time and defeats the purpose of using KMP.

Expert Zone

1

The LPS array can be reused for multiple searches with the same pattern, saving preprocessing time in repeated queries.

2

KMP's linear time guarantee holds even for worst-case inputs with repeated patterns, unlike some hashing-based algorithms.

3

The algorithm's efficiency depends on the pattern's structure; highly repetitive patterns produce larger LPS values, affecting shifts.

When NOT to use

Avoid KMP when the pattern changes frequently and preprocessing overhead is costly; in such cases, algorithms like Rabin-Karp with rolling hash or Boyer-Moore with good average-case performance may be better.

Production Patterns

KMP is used in text editors for 'find' functionality, DNA sequence analysis for motif searching, network intrusion detection for pattern matching in data streams, and plagiarism detection tools where exact substring matches are needed efficiently.

Connections

Finite Automata

KMP's LPS array corresponds to states in a finite automaton that recognizes the pattern.

Understanding KMP as a finite automaton helps grasp how pattern matching can be modeled as state transitions.

Hashing Algorithms

Both KMP and hashing algorithms like Rabin-Karp solve pattern matching but use different strategies: deterministic prefix info vs probabilistic hashing.

Knowing both approaches helps choose the right tool based on accuracy and performance needs.

Human Memory Recall

KMP's use of previously matched pattern parts to skip ahead is similar to how humans recall partial information to avoid re-learning from scratch.

This connection shows how efficient algorithms mimic natural cognitive shortcuts.

Common Pitfalls

#1 Incorrectly building the LPS array by resetting length to zero too early.

Wrong approach:

if (pattern.charAt(i) != pattern.charAt(length)) {
length = 0;
lps[i] = 0;
i++;
}

Correct approach:

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

Root cause:

Misunderstanding that length should fallback to previous LPS value instead of resetting immediately.

#2 Advancing text index i even when pattern index j can be shifted using LPS after mismatch.

Wrong approach:

if (pattern.charAt(j) != text.charAt(i)) {
i++;
j = 0;
}

Correct approach:

if (pattern.charAt(j) != text.charAt(i)) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}

Root cause:

Not using LPS to shift pattern index j properly, causing unnecessary text index increments.

#3 Not handling the case when pattern is empty or null before running KMP.

Wrong approach:

public void search(String text, String pattern) {
// no checks
int[] lps = computeLPS(pattern);
...
}

Correct approach:

public void search(String text, String pattern) {
if (pattern == null || pattern.length() == 0) {
System.out.println("Empty pattern");
return;
}
int[] lps = computeLPS(pattern);
...
}

Root cause:

Ignoring edge cases leads to runtime errors or incorrect behavior.

Key Takeaways

KMP algorithm speeds up pattern searching by using the pattern's own structure to avoid repeated comparisons.

The Longest Prefix Suffix (LPS) array is the core preprocessing step that encodes how the pattern overlaps with itself.

During search, KMP uses the LPS array to decide how far to shift the pattern on mismatches, ensuring linear time complexity.

Understanding how to build and use the LPS array is essential to implementing KMP correctly.

KMP is a deterministic, efficient algorithm suitable for exact pattern matching in many real-world applications.

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