字符串匹配

####　字符串匹配小结

1. kmp算法

   private int[] makeNext(char[] arr) {
    int len = arr.length();
    int [] next = new int[len];
       
    next[0] = -1;
    for (int i =0,j=-1;i+1 < len;){
        if(j ==-1 || arr[i] == arr[j]){
            next[i+1] = j+1;
            if(arr[i+1] == arr[j+1]) next[i+1] = next[j+1];
            i++;
            j++;
        }
        if(arr[i] != arr[j]) j = next[j];
    }
    return next;
   }
   

   构建next数组时,初始化next[0]=-1,next[1]=0,-1在此只是用来标记状态，用来表示此时需要将主串中的游标右移，（在主串匹配是如果遇到next[j] = -1,是不是表明主串中存在从串中不存在的字符？？),
   next[1] = 0,很好理解，即从串needle[1]失配时，需要用needle[0]进行匹配