import java.util.ArrayList;
public class KMP {
//主串
static String str = "1kk23789456789hahha";
//模式串
static String ch = "789";
static int next[] = new int[20];
public static void main(String[] args) {
setNext();
ArrayList<Integer> arr = getKmp();
if(arr.size()!=0) {
for(int i=0; i<arr.size(); i++) {
System.out.println("匹配發生在:"+arr.get(i));
}
}else {
System.out.println("匹配不成功");
}
}
private static void setNext() {
// TODO Auto-generated method stub
int lenCh = ch.length();
next[0] = 0;
next[1] = 1;
//k表示next[i-1]的值
int k = 0;
for(int i=2; i<=lenCh; i++) {
k = next[k];
/*
* 這個while循環的作用找個例子看看就好理解了
* 我認為是每次找最長，一旦成功就停止，保證找到的是當前最長
*/
while(k!=0 && ch.charAt(i-1)!=ch.charAt(k)) {
k = next[k];
}
if(ch.charAt(i-1)==ch.charAt(k)) {
k++;
}//else就是k=0
//不是next[k] = k，i表示有幾個字符的前綴
next[i] = k;
}
}
private static ArrayList<Integer> getKmp() {
// TODO Auto-generated method stub
ArrayList<Integer> arr = new ArrayList<Integer>();
int lenStr = str.length();
int lenCh = ch.length();
//主串開始的匹配位置
int pos = 0;
//模式串每次匹配位置
int k = 0;
//循環條件不是k<lenCh,這樣的話可能死循環(沒有匹配發生)
while(pos<lenStr) {
/*
* 首次進入沒什么大作用，做要是為提高以后的匹配效率
* 寫在最后一行也行
*/
k = next[k];
while(k<lenCh && str.charAt(pos)==ch.charAt(k)) {
pos++;
k++;
}
if(lenCh==k) {
arr.add(pos-k);
}else if(0==k) {
/*
* 不加這一句死循環
* 因為next[0] = 0
* 比如abcd和abce，到de不匹配，此時執行k = next[k](k=3),
* k變為0，發現d和a不匹配，此時k還是0，重復執行以上步驟，那么死循環了
*/
pos++;
}//實際上else就是k = next[k]，所以才說k = next[k]寫在最后一行也行
}
return arr;
}
}
