public class KMP {
private String needle;
private int[][] dfa;
public KMP(String needle) {
//Build DFA from pattern.
this.needle = needle;
int M = needle.length();
int R = 256;
dfa = new int[R][M];
dfa[needle.charAt(0)][0] = 1;
for(int x = 0, j = 1; j < M; j++) {
//comput dfa[][j]
for(int c = 0; c < R; c++) {
dfa[c][j] = dfa[c][x]; //copy mismatch cases.
}
dfa[needle.charAt(j)][j] = j + 1; //set match case.
x = dfa[needle.charAt(j)][x]; //update restart state.
}
}
public int search(String haystack) {
//Simulate operation of DFA on haystack
int i, j, N = haystack.length(), M = needle.length();
for(i = 0, j = 0; i < N && j < M; i++) {
j = dfa[haystack.charAt(i)][j];
}
if(j == M) return i - M;
else return -1;
}
public static void main(String...args) {
String haystack = "search a needle in a haystack.";
KMP kmp = new KMP("needle");
System.out.println(kmp.search(haystack));
}
}
