KMP.java

/**
 * This code is to conduct pattern matching of given str and pattern
 *
 * @Author Gyeong - lemidia
 */

public class KMP {
 public static void kmp (String str, String pattern) {
 int lps[] = LPS(pattern);
 int i = 0;
 int j = 0;

 while (i < str.length()) {
 if (str.charAt(i) == pattern.charAt(j)) {
 if (j == pattern.length() - 1) {
 int foundIdx = i - pattern.length() + 1;
 System.out.println("The pattern was found at index " + foundIdx + " of the text.");
 i++;
 j = lps[j];
 } else {
 i++;
 j++;
 }
 } else {
 if (j == 0)
 i++;
 else
 j = lps[j-1];
 }
 }
 }

 // Construct an LPS array that represents proper
 // prefix which is also suffix of the given pattern
 public static int[] LPS (String pattern) {
 int lps[] = new int[pattern.length()];
 int i = 1;
 int j = 0;

 // While less than lps or pattern length
 while (i < lps.length) {
 if (pattern.charAt(j) == pattern.charAt(i)) {
 lps[i] = j + 1;
 i++;
 j++;
 } else {
 // There is no more space to go to left
 // So, just increment the i's index by 1
 if (j == 0)
 i++;
 // We go to the previous index.
 // And look up Longest proper prefix which is
 // also suffix of previous string
 // And Let this be j
 else
 j = lps[j-1];
 }
 }
 return lps;
 }
 public static void main(String[] args) {
 String str = "abababacd";
 String pattern = "aba";
 /*
 
 Output:
 The pattern was found at index 0 of the text.
 The pattern was found at index 2 of the text.
 The pattern was found at index 4 of the text.
 
 */
 kmp(str, pattern);
 }
}