KMP算法尊流，左神P12。
KMP的例子流程講解.PNG
public static int getindexof(String s,String m){
if(s==null || m==null || m.length()<1 || s.length()<m.length()){
return -1;
}
char[] s1 = s.toCharArray();
char[] s2 =m.toCharArray();
int i1=0;
int i2=0;
int[] next = getNextArray(s2);
while(i1<s1.length && i2<s2.length){
if(s1[i1]==s2[i2]){ //相等同時移動
i1++;
i2++;
}else if(next[i2]==-1){ // next數組中規(guī)定0位置就是-1
i1++; //str2沒法再找到位置移動了膘魄，str1必須后移，后移之后和0位置的比較
}else{
i2 = next[i2]; //不想等str2可以找到next數組的位置竭讳，str2移動到next的位置繼續(xù)和str1[i]比較创葡，str1不動
}
}
//i1 或者i2越界
//i2越界表示找到匹配位置了，否則就是沒找到啊绢慢，返回-1
return i2==s2.length ? i1-i2:-1;
}
/*
abbstabbecabbstabb ? _
i-1 i
8 求解
灿渴？處的next數組值為8表示最長前綴和后綴是8（abbstabb）
求解i處的next數組和i自己的值沒有關系，只看i-1位置的數
由next數組的8可以得到接下來要比較的元素是e和胰舆？ 如果兩者相等那么i的next數組就是8+1=9
否則逻杖，繼續(xù)跳轉，就是去8的下標處繼續(xù)比較就是e（它的next數組是3）（abb）
繼續(xù)這個流程思瘟，找到next數組的待比較元素就是s荸百，和？比較滨攻，相等3+1結束够话，不相等繼續(xù)
調到s找到next數組對應的待比較元素（s的下標是0），那么a=光绕？嘛女嘲？ 如果等于就是1了，
不等于a的next數組是-1诞帐，找不到了欣尼，直接i的next數組的值就是0
*/
public static int[] getNextArray(char[] ms){
if(ms.length==1){
return new int[]{-1};
}
int[] next = new int[ms.length];
next[0]=-1;
next[1] = 0;
int i=2;
int cn =0; //當前字符和？字符（i-1字符）比較
while(i<next.length){
if(ms[i-1]==ms[cn]){ //當cn==0的時候呢這里就已近比較了next[0]和？的數據愕鼓，所以是>0,而不是>=0
next[i++] = ++cn; //當前位置和i-1的字符相等了钙态，那么cn+1填入即可。cn隨著i值需要自增菇晃，才能保證下一個是i-1的位置
}else if(cn>0){ //不相等呢册倒，繼續(xù)通過next數組找下一個比較的位置。
cn = next[cn]; //這里cn>0 cn==0的話 cn=next[cn]就是是-1磺送，到上面就會報錯
}else{
next[i++] = 0; //既不相等cn又到了0的位置那么就是沒得比了驻子，
}
}
return next;
}
