2022-03-13

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数组中规定0位置就是-1
                i1++;   //str2没法再找到位置移动了，str1必须后移，后移之后和0位置的比较
            }else{
                i2 = next[i2];   //不想等str2可以找到next数组的位置，str2移动到next的位置继续和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
       否则，继续跳转，就是去8的下标处继续比较就是e（它的next数组是3）（abb）
       继续这个流程，找到next数组的待比较元素就是s，和？比较，相等3+1结束，不相等继续
       调到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){    //不相等呢，继续通过next数组找下一个比较的位置。
                cn = next[cn];   //这里cn>0 cn==0的话 cn=next[cn]就是是-1，到上面就会报错
            }else{
                next[i++] = 0;  //既不相等cn又到了0的位置那么就是没得比了，
            }
        }
        return next;
    }