package com.trs.utils;

public class KMPStr {

    /*

     * 在KMP算法中，最难求的就是next函数，如何理解next函数是一个难题，特别是k=next[k]，这里

     * 需要指出的是当p[i]!=p[j]时，我们只有通过回溯将k的值逐渐减小，貌似类似与用到了动态规划的思想 参考网上阮一峰老师的博客讲解的十分详细

     */

    private static int[] getNext(String t) {

        int[] next = new int[t.length()];

        next[0] = -1;

        int j = 0;

        int k = -1;

        while (j < t.length() - 1) {

            if (k == -1 || t.charAt(j) == t.charAt(k)) {

                j++;

                k++;

                next[j] = k;

            } else {

                k = next[k];

            }

        }

        for (int i : next) {

            System.out.print(i + ":");

        }

        System.out.println();

        return next;

    }

    public static int kmpStrIndex(String s, String t, int[] next) {

        int i = 0;

        int j = 0;

        while (i < s.length() && j < t.length()) {

            if (j == -1 || s.charAt(i) == t.charAt(j)) {

                i++;

                j++;

            } else {

                // i不变，j后退

                j = next[j];

            }

            if (j == t.length()) {

                return i - j;

            }

        }

        return -1;

    }

}