Building the LPS Array for KMP

1. The KMP Idea: Smarter Shifts

First, let's understand the problem KMP solves. A naive, brute-force search algorithm is inefficient because when a mismatch occurs, it shifts the pattern by only one position and starts comparing from the beginning. This leads to many redundant comparisons, especially in patterns with repeating characters.

The core insight of KMP is: when a mismatch happens after matching k characters of the pattern, we already know what those k characters of the text look like. Instead of dumbly shifting by one, we can use pre-computed information about the pattern to make a much larger, "smarter" shift, bypassing positions that could not possibly result in a match. This eliminates the need to ever move the text pointer backward.

To see this inefficiency in action, let's watch a video that explains the drawbacks of the naive approach.

2. The LPS Array: Encoding the Pattern's Structure

The "pre-computed information" that enables these smart shifts is stored in an array, typically called the LPS array.

LPS stands for "Longest Proper Prefix which is also a Suffix".

Let's break that down:

• Prefix: A substring starting from the beginning. For "abcd", the prefixes are "a", "ab", "abc", "abcd".
• Suffix: A substring ending at the end. For "abcd", the suffixes are "d", "cd", "bcd", "abcd".
• Proper Prefix: A prefix that is not the entire string itself. For "abcd", the proper prefixes are "a", "ab", "abc".

The LPS array for a pattern P of length M is an array of size M where lps[i] stores the length of the longest proper prefix of the substring P[0...i] that is also a suffix of P[0...i].

This might sound complex, so let's see it in action. The following video provides a clear, example-driven introduction to what this array represents.

Let's do one more example by hand for the pattern P = "ababa":

• i = 0: P[0...0] is "a". No proper prefixes. lps[0] = 0.
• i = 1: P[0...1] is "ab". Proper prefix is "a". Suffix is "b". No match. lps[1] = 0.
• i = 2: P[0...2] is "aba". Proper prefixes: "a", "ab". Suffixes: "a", "ba". The longest match is "a". Length is 1. lps[2] = 1.
• i = 3: P[0...3] is "abab". Proper prefixes: "a", "ab", "aba". Suffixes: "b", "ab", "bab". The longest match is "ab". Length is 2. lps[3] = 2.
• i = 4: P[0...4] is "ababa". Proper prefixes: "a", "ab", "aba", "abab". Suffixes: "a", "ba", "aba", "baba". The longest match is "aba". Length is 3. lps[4] = 3.

So, the final LPS array for "ababa" is [0, 0, 1, 2, 3]. This array tells the KMP search algorithm that after matching "ababa", if the next character fails, the text has a suffix "aba" which matches the prefix of our pattern, so we don't need to recheck everything.

3. The Algorithm to Construct the LPS Array

We can build the LPS array efficiently in O(M) time using a clever two-pointer approach. Let M be the pattern length.

We use two integer variables:

• i: Iterates through the pattern from index 1 to M-1. We are trying to compute lps[i].
• len: Stores the length of the longest proper prefix-suffix for the previous index, i-1. It also serves as a pointer to the character in the prefix we're trying to match.

The logic revolves around comparing pattern[i] and pattern[len]. The following article explains the algorithm beautifully.

To summarize the logic you just read:

1. Match (pattern[i] == pattern[len]): We've extended the prefix-suffix match. We increment len, set lps[i] = len, and move to the next character by incrementing i.
2. Mismatch (pattern[i] != pattern[len]):
   • If len > 0: We can't extend the current prefix. We need to try a shorter prefix. The length of the next-best prefix is already computed and stored in lps[len - 1]. So we "fall back" by setting len = lps[len - 1] and repeat the comparison for the same i with the new, shorter len.
   • If len == 0: We've fallen back as far as possible. No prefix matches. We set lps[i] = 0 and move to the next character by incrementing i.

4. Java Implementation

Now let's translate this logic into Java code. As you'll see, the if-else structure maps directly to the three cases we just discussed.

The code you just reviewed is a concise and efficient implementation of the LPS construction algorithm. The fallback step, len = lps[len - 1], is the most crucial part. It allows the algorithm to reuse its own past results to avoid re-computing from scratch, which is what gives it its linear time complexity.

5. Complexity Analysis

• Time Complexity: O(M), where M is the length of the pattern.
  While the while loop contains a mechanism (len = lps[len - 1]) where the inner pointer len can go backward, the outer pointer i always moves forward. The len pointer can only be decremented as many times as it has been incremented. This is a classic case for amortized analysis, which shows that the total number of operations is proportional to M.

• Space Complexity: O(M). We need an auxiliary array of size M to store the LPS values.

Conclusion

Congratulations! You've successfully learned how to construct the LPS array, the fundamental building block of the KMP algorithm. This preprocessing step captures the internal overlapping structure of a pattern, which is the key to avoiding redundant comparisons during the search phase.

Key Takeaways:

• The KMP algorithm guarantees O(N+M) time complexity by using pre-computation to make intelligent shifts.
• The LPS array is the result of this pre-computation. lps[i] stores the length of the longest proper prefix of pattern[0...i] that is also a suffix.
• The LPS array can be constructed in O(M) time and O(M) space using an efficient two-pointer algorithm.
• The fallback step (len = lps[len-1]) is the core of the construction algorithm, allowing it to reuse previous results.

Preview of the next lesson:
Now that we have this powerful tool, the next logical step is to use it. In our next lesson, you will implement the KMP pattern matching algorithm using the precomputed LPS array to perform the actual search in a text, completing your mastery of this cornerstone algorithm.