/** * 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); } }

KMP2