package othercode.Array;

/**
 * KMP字符串匹配
 */
public class KMPSearch {
    //构建dp数组，含义为pat的状态转移数组，
    // dp[j][c] = next 代表j状态在遇到字符c时应转移的next状态
    // j代表当前的状态, c代表遇到的字符（ASCII 码）
    private int[][] dp;
    private String pat;

    public KMPSearch(String pat) {
        this.pat = pat;
        int M = pat.length();
        //dp[状态][字符]=下个状态
        dp = new int[M][256];
        //base case.只有遇到pat的第一个字符，才会进到状态1
        dp[0][pat.charAt(0)] = 1;
        //初始化影子状态X
        int X = 0;
        for (int j = 1; j < M; j++) {
            for (int c = 0; c < 256; c++) {
                if (pat.charAt(j) == c) {
                    //状态推进
                    dp[j][c] = j + 1;
                } else {
                    //状态重启，委托影子状态X进行计算
                    dp[j][c] = dp[X][c];
                }
            }
            //更新下一次的影子状态，为本次影子状态遇见本次字符的状态
            //这样下一个状态重启时，找到的就是本次（上一次）遇见字符的状态
            X = dp[X][pat.charAt(j)];

        }


    }

    public int search(String txt) {
        if (null == txt || pat == null) return -1;
        int M = pat.length();
        int N = txt.length();
        //初始化pat的状态
        int j = 0;
        for (int i = 0; i < N; i++) {
            //遍历整个txt，根据txt的字符获取pat的状态转移
            j = dp[j][txt.charAt(i)];
            //达到终止态，返回匹配开头的索引
            if (j == M) return i - M + 1;
        }
        //没达到终止态，匹配失败，返回-1
        return -1;
    }

}