int[] next ;
    /**
     * 初始化next數(shù)組
     * @param modelStr
     */
    public void init(char[] modelStr) {
        //首先計算next數(shù)組
        //遍歷modelStr，遍歷到的字符與之前字符組成一個串
        next = new int[modelStr.length];
        int start = 0;
        while (start < modelStr.length) {
            next[start] = this.recursion(start, modelStr);
            ++ start;
        }
    }

    /**
     *
     * @param i 當(dāng)前遍歷到的字符
     * @return
     */
    private int recursion(int i, char[] modelStr) {
        //next記錄的是個數(shù)，不是下標(biāo)
        if (0 == i) {
            return 0;
        }
        int last = next[i -1];
        //沒有匹配的,直接判斷第一個是否匹配
        if (0 == last) {
            if (modelStr[last] == modelStr[i]) {
                return 1;
            }
            return 0;
        }
        //如果last不為0，有值，可以作為最長匹配的前綴
        if (modelStr[last] == modelStr[i]) {
            return next[i - 1] + 1;
        }
        //當(dāng)next[i-1]對應(yīng)的子串的下一個值與modelStr不匹配時，需要找到當(dāng)前要找的最長匹配子串的次長子串
        //依據(jù)就是次長子串對應(yīng)的子串的下一個字符==modelStr[i];
        int tempIndex = i;
        while (tempIndex > 0) {
            last = next[tempIndex - 1];
            //找到第一個下一個字符是當(dāng)前字符的匹配子串
            if (modelStr[last] == modelStr[i]) {
                return last + 1;
            }
            -- tempIndex;
        }
        return 0;
    }

public int kmp(char[] mainStr, char[] modelStr) {
        //開始進行匹配
        int i = 0, j = 0;
        while (i + modelStr.length <= mainStr.length) {
            while (j < modelStr.length) {
                //找到第一個不匹配的位置
                if (modelStr[j] != mainStr[i]) {
                    break;
                }
                ++ i;
                ++ j;
            }
            if (j == modelStr.length) {
                //證明完全匹配
                return i - j;
            }
            //走到這里找到的是第一個不匹配的位置
            if (j == 0) {
                ++ i;
                continue;
            }
            //從好前綴后一個匹配
            j = next[j - 1];
        }
        return -1;
    }