【无标题】

package kmp;

// 看毛片算法实现
public class Kmp {
    
    public static int[] getNext(String dest){
        // 有一点细节需要注意, next[] 中的连续位置的数据最多出现 +1 的递增,不会突然增量突变,如果增量突变,那么一定是求错了;
        int len = dest.length();
        int[] next = new int[len];
        next[0] = -1;
        next[1] = 0;
        int k = 0; // 假设 next[j-1] = k;
        int j = 2;
        // 这个类似与动态规划算法,像是从前向后递推,后面的问题的解,依赖前面的解的结果;
        while(j < len){
            if(k == -1 || dest.charAt(k) == dest.charAt(j-1)){ // dest[k] == dest[j] || 回退到了起始位置了;
                next[j] = k+1;
                k++;
                j++;
            }else { // dest[k] != dest[j] (一直回退到,能够相同)
                k = next[k];
            }
        }
        return next;
    }
    
    public static int SubString(String src,String dest,int pos){
        if(src == null || dest == null) return -1;
        int srcLen = src.length();
        int destLen = dest.length();
        if(srcLen == 0|| destLen == 0 || pos >= srcLen) return -1;
        int[] next = getNext(dest);
        int i = pos; // 被匹配串的位置;
        int j = 0;  // 匹配串起始位置

        while(i < srcLen && j < destLen){
            if( j == -1 || src.charAt(i) == dest.charAt(j)){ // j == -1 为了和 next[] 向照应,即第一次匹配就失败,回退到下标-1;
                i++;
                j++;
            }else {
                j = next[j];
            }
        }// 出了这个循环,要么 i >= srcLen 要么 j >= destLen 要么 之前两个条件都满足;
        // 我们只关心 是 j 的情况;
        if(j >= destLen) return i - j; // 找到了,匹配结束 ;
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(SubString("abcccadadada","cca",8));
    }
}