public static int[] getNexts(char[] tt)

    {

        int[] nexts = new int[tt.length];

        nexts[0] = 0;

        // 从1到结束, 挨个计算next

        for (int i = 1; i < tt.length; i++)

        {

            // 在给定的子串里, 记录matched时, 最大的长度值

            for (int j = 0; j < i; j++)

            {

                boolean matched = true;

                // 使用 k, 依次比较从 0  到 j 和从 i-j 到  i的字符是否相等, 注意下标都是从小往大移动

                for (int k = 0; k <= j; k++)

                {

                    if (tt[k] != tt[i-j+k])

                    {

                        matched = false;

                        break;

                    }

                }

                // 匹配的, 记录最大长度

                if (matched)

                {

                    int length = j + 1;

                    if (nexts[i] < length)

                        nexts[i] = length;

                }

            }

        }

        return nexts;

    }

    /**

     * 只使用两个起始下标, 来计算和记录next序列

     *

     * @param tt

     * @return

     */

    public static int[] getNexts2(char[] tt)

    {

        int[] nexts = new int[tt.length];

        nexts[0] = 0;

        // 前缀起始下标

        int prefix = 0;

        // 后缀起始下标

        int suffix = prefix + 1;

        // 匹配长度

        int len = 0;

        while(suffix < tt.length)

        {

            if (tt[prefix] == tt[suffix])

            {

                // 如果匹配, 则记录下当前的next最大值, 并且将前缀和后缀下标都往大移动一位

                prefix++;

                len++;

                if (nexts[suffix] < len)

                    nexts[suffix] = len;

            }

            else

            {

                // 如果不匹配, 则当前长度归零, 并且前缀回归起点, 而后缀依然往后走

                len = 0;

                prefix = 0;

            }

            suffix++;

        }

        return nexts;

    }

    public static int kmpFind(char[] ss, char[] tt)

    {

        // 内容串下标

        int spos = 0;

        // 搜索串下标

        int tpos = 0;

        // 计算next序列

        int[] nexts = getNexts2(tt);

        while (spos < ss.length)

        {

            if (ss[spos] == tt[tpos])

            {

                // 匹配上后, 判断是否满足退出条件

                if (tpos == tt.length - 1) return spos - tt.length + 1;

                if (tpos == ss.length - 1) return -1;

                // 否则继续往后匹配

                spos++;

                tpos++;

            }

            else

            {

                // 未匹配的情况下, 如果搜索串是第一步都未中, 则内容串下标继续移动

                if (tpos == 0)

                    spos++;

                // 否则调整搜索串下标到前一步的next值(忽略掉最大前缀)

                else

                    tpos = nexts[tpos - 1];

            }

        }

        return -1;

    }