KMP Algorithm

The Knuth-Morris-Pratt (KMP) algorithm is an efficient string matching algorithm that searches for occurrences of a pattern within a text. It improves upon the naive approach by avoiding unnecessary comparisons, using information gathered from previous comparisons to skip sections of the text.

How it Works

The KMP algorithm preprocesses the pattern to create a longest prefix-suffix (LPS) array, which is used to determine how many characters can be skipped when a mismatch occurs. This allows the algorithm to achieve a time complexity of O(n + m), where n is the length of the text and m is the length of the pattern.

Java Example

Here is a simple implementation of the KMP algorithm in 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);
    int index = KMPSearch(text, pattern, lps);
    System.out.println("Pattern found at index: " + index);
  }

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

  public static int KMPSearch(String text, String pattern, int[] lps) {
    int i = 0;
    int j = 0;
  }

}