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;
 }

}