KMP Algorithm with LPS Array

1. The KMP Search Logic: Intelligent Shifts in Action

The KMP search algorithm uses two pointers:

• i: A pointer for the text string (let's call it txt). It always moves forward, never backward.
• j: A pointer for the pattern string (pat). This pointer tracks how much of the pattern we have matched so far.

We iterate through the text with i while trying to match the pattern with j. The magic of KMP happens when a mismatch occurs. Instead of resetting our progress, we use the lps array to perform an intelligent shift.

Let's watch a video that explains the main algorithm. It demonstrates how the pointers i and j interact and how the precomputed array guides the search after a mismatch.

2. The Search Algorithm in Detail

As you saw in the video, the search loop revolves around comparing txt.charAt(i) and pat.charAt(j). This leads to three main cases:

Case 1: Characters Match
If txt.charAt(i) == pat.charAt(j), it means we've extended our match. We simply increment both pointers: i++ and j++.

Case 2: A Full Pattern Match is Found
After incrementing, if j becomes equal to the pattern's length (M), we have found a complete match!

1. Record the starting index of the match, which is i - j.
2. Important: We don't stop here. To find subsequent overlapping matches, we must shift the pattern. We do this by setting j = lps[j - 1]. This repositions the pattern to the longest proper prefix that is a suffix of the entire pattern, allowing the search to continue seamlessly.

Case 3: Characters Mismatch
If txt.charAt(i) != pat.charAt(j), we consult the lps array.

• If j > 0: We can't extend the current partial match. However, the lps array tells us that a shorter prefix of the pattern might still align with the text. The length of this shorter prefix is lps[j-1]. So, we update j = lps[j - 1]. We do not increment i. We are effectively sliding the pattern forward and retrying the comparison with the current character txt.charAt(i) against a new character in the pattern.
• If j == 0: The mismatch occurred at the very first character of the pattern. There's no shorter prefix to fall back to. We have no choice but to move to the next character in the text. We simply increment i.

3. Java Implementation

Now, let's look at how this logic is implemented in Java. The following resource provides a clean and well-commented implementation of the KMP search function, which takes the text, the pattern, and the pre-computed lps array.

Here's the core search logic from the article, with added comments to connect it back to our three cases. In a real-world scenario, you would have a method computeLPSArray that you wrote in the last lesson and call it before starting the search.

class KMP_Search {

    // The LPS array construction method from the previous lesson
    void computeLPSArray(String pat, int M, int lps[]) {
        int length = 0;
        int i = 1;
        lps[0] = 0; // lps[0] is always 0

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

    // The KMP search algorithm
    void KMPSearch(String pat, String txt) {
        int M = pat.length();
        int N = txt.length();

        // Create lps[] that will hold the longest prefix suffix values for pattern
        int lps[] = new int[M];
        int j = 0; // index for pat[]

        // Preprocess the pattern to calculate lps[] array
        computeLPSArray(pat, M, lps);

        int i = 0; // index for txt[]
        while (i < N) {
            // ---- Case 1: Characters Match ----
            if (pat.charAt(j) == txt.charAt(i)) {
                j++;
                i++;
            }
            
            // ---- Case 2: A Full Pattern Match is Found ----
            if (j == M) {
                System.out.println("Found pattern at index " + (i - j));
                // To find other occurrences, we continue searching.
                // We shift the pattern using the lps value of the last element.
                j = lps[j - 1]; 
            } 
            
            // ---- Case 3: Mismatch after some matches ----
            else if (i < N && pat.charAt(j) != txt.charAt(i)) {
                // Don't match lps[0..lps[j-1]] characters,
                // they will match anyway.
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    // Mismatch at the very first character of the pattern
                    i = i + 1;
                }
            }
        }
    }
}

4. Complexity Analysis

• Time Complexity: O(N + M)

  • The computeLPSArray function takes O(M) time, as we saw in the last lesson.
  • The KMPSearch loop processes the text. The pointer i is always incremented and never goes back. The pointer j can go back, but the number of times it can be decremented is bounded by the number of times it has been incremented. Amortized analysis shows that the search phase takes O(N) time.
  • Therefore, the total time complexity is O(M) + O(N) = O(N + M).

• Space Complexity: O(M)

  • We need an auxiliary array lps of size M to store the preprocessing results. The search itself uses a constant amount of extra space for the pointers.

Conclusion

You have now fully implemented the Knuth-Morris-Pratt algorithm! By combining the LPS array construction with the intelligent search logic, you can now solve the pattern matching problem with a guaranteed linear time complexity, which is a major achievement and a staple of technical interviews.

Key Takeaways:

• The KMP search uses two pointers, i for the text and j for the pattern. The text pointer i never backtracks.
• When characters match, both pointers advance.
• When a mismatch occurs, the lps array is used to find the optimal shift for the pattern pointer j (j = lps[j-1]), avoiding redundant comparisons.
• The algorithm's total time complexity is O(N+M), making it highly efficient for all cases.

Preview of the next lesson:
This lesson concludes our deep dive into advanced string algorithms. We will now shift gears and move on to a fundamental, pointer-based data structure that is crucial for interview preparation: Linked Lists. In the next lesson, you will learn to implement a singly linked list with insertion, deletion, and traversal operations.