How to Implement the KMP (Knuth-Morris-Pratt) Algorithm

Introduction

The KMP (Knuth-Morris-Pratt) algorithm is an efficient method for pattern searching in strings. Unlike the naive approach, which may re-check characters unnecessarily, the KMP algorithm avoids redundant comparisons by pre-processing the pattern. It constructs a partial match table (also known as the “lps” array) that guides the search process, resulting in a time complexity of O(n + m), where n is the length of the text and m is the length of the pattern.

How the KMP Algorithm Works

The KMP algorithm operates in two main phases. First, it pre-processes the pattern to build the longest prefix-suffix (LPS) array. This array records the length of the longest prefix that matches a suffix for each prefix of the pattern, excluding the full match itself. Second, it uses this LPS array while scanning the text to skip unnecessary character comparisons.

Building the LPS Array

The LPS array is built by comparing characters within the pattern itself. For each position in the pattern, it records the length of the longest prefix that is also a suffix ending at that position. This allows the algorithm to know how much to shift the pattern upon encountering a mismatch during the search.

Pattern Search Using LPS

Once the LPS array is constructed, the algorithm begins comparing the pattern to the text. On a character match, both text and pattern indices advance. On a mismatch, instead of restarting from the next character in the text, the pattern index is updated using the lps array, thus maintaining linear time complexity.

Java Implementation

Below is a complete Java example demonstrating the KMP algorithm in action. It includes methods to compute the lps array and to search for the pattern in the given text.

class KMPAlgorithmUnitTest {

	@Test
	public void kmpTest() throws Exception {
		String text = "ABABDABACDABABCABAB";
		String pattern = "ABABCABAB";
		search(text, pattern);
	}

	private void search(String textToSearch, String stringPattern) {
		int n = textToSearch.length();
		int m = stringPattern.length();
		int[] longestPrefixSuffix = computeLPSArray(stringPattern);

		int i = 0; // index for text
		int j = 0; // index for pattern

		while (i < n) {
			if (stringPattern.charAt(j) == textToSearch.charAt(i)) {
				i++;
				j++;
			}

			if (j == m) {
				System.out.println("Pattern found at index " + (i - j));
				j = longestPrefixSuffix[j - 1];
			} else if (i < n && stringPattern.charAt(j) != textToSearch.charAt(i)) {
				if (j != 0) {
					j = longestPrefixSuffix[j - 1];
				} else {
					i++;
				}
			}
		}
	}

	private int[] computeLPSArray(String stringPattern) {
		int m = stringPattern.length();
		int[] longestPrefixSuffix = new int[m];
		int len = 0; // length of the previous longest prefix suffix
		int i = 1;

		while (i < m) {
			if (stringPattern.charAt(i) == stringPattern.charAt(len)) {
				len++;
				longestPrefixSuffix[i] = len;
				i++;
			} else {
				if (len != 0) {
					len = longestPrefixSuffix[len - 1];
				} else {
					longestPrefixSuffix[i] = 0;
					i++;
				}
			}
		}
		return longestPrefixSuffix;
	}
}

Conclusion

The KMP algorithm is a powerful tool for pattern matching, particularly when processing large texts and conducting multiple pattern searches. Its efficiency stems from pre-processing the pattern, allowing it to skip characters that have already been matched. Using the LPS array ensures linear time complexity and eliminates unnecessary re-comparisons, making it significantly faster than the naive approach in many cases.

You can find the example code on Github.