/**
* Created by xie on 14-8-24.
*/
public class KMP {
private String pat;
private int M;
private int R=256;
private int dfa[][];

public KMP(String pat){
M=pat.length();
dfa=new int[R][M];
dfa[pat.charAt(0)][0]=1;
for(int X=0,j=1;j<M;j++){
for(int c=0;c<R;c++) dfa[c][j]=dfa[c][X]; //set mismatch
dfa[pat.charAt(j)][j]=j+1; //set match
X=dfa[pat.charAt(j)][X]; //update X
}
}

public int search(String text){
int N=text.length();
int i,j;
for(i=0,j=0;i<N&&j<M;i++){
j=dfa[text.charAt(i)][j];
}
if(j==M) return i-M;
else return -1;
}

public static void main(String[] args) {
String pat="abac";
String text="abadabadd";

KMP matcher=new KMP(pat);
int index=matcher.search(text);
System.out.println(index);
}
}

KMP