题解 | #二维数组的kmp算法#

稍微看了下别人的题解，反正我是从来都记不住next数组是怎么计算的。。。
此解法来自labuladong大佬最基础的kmp：利用状态机的思想，当字符匹配的时候推进状态；当字符不匹配的时候要回到某个状态（有相同前缀的状态）
二维数组虽然增加了空间复杂度，但是好理解多了好嘛

class KMP {
    private String pattern;
    private int[][] dp;
    private int n;

    public KMP(String pattern) {
        this.pattern = pattern;
        this.n = pattern.length();
        this.dp = new int[n + 1][256];    // 因为匹配完模式串之后，还要继续往后匹配，所以这里第一维的长度是n+1
        init();
    }

    // 如果是找到子串出现的次数，则在匹配完之后，回到最后状态的影子状态
    private void init() {
        int X = 0;    // 影子状态：即模式串要“重启”到的位置，影子状态总是落后最新状态（search时的j）一个状态，并和j拥有最长的相同前缀
        dp[0][pattern.charAt(0)] = 1;    // 只有第一个字符匹配时才能向前推进状态，遇到其他字符不推进
        for (int i = 1; i < n; i++) {    // 0已经处理过了，这里就从1开始
            for (int c = 0; c < 256; c++) {
                if (c == pattern.charAt(i)) dp[i][c] = i + 1;    // 如果匹配，则状态向前推进1位
                else dp[i][c] = dp[X][c];    // 利用影子状态重启
            }
            X = dp[X][pattern.charAt(i)];    // 推进影子状态
        }
        dp[n][pattern.charAt(n - 1)] = X;    // 因为这里是计算出现次数，所以在匹配完之后，要额外记录一下匹配完之后应该回到的影子状态
    }

    public int search(String str) {
        int ln = str.length();
        int j = 0;    // 模式串的初始状态
        int r = 0;    // 记录出现的次数
        for (int i = 0; i < ln; i++) {    
            j = dp[j][str.charAt(i)];  // 推进模式串的状态
            if (j == n) {    // 匹配完了就计数器+1并回到最近的影子状态
                r++;
                j = dp[j][str.charAt(i)];
            }
        }
        return r;
    }
}

public class Solution {
    public static void main(String[] args) {
        String pattern = "aabaa";
        String str = "aabaabaa";
        System.out.println(new Solution().kmp(pattern, str));
    }

    public int kmp(String S, String T) {
        KMP kmp = new KMP(S);
        return kmp.search(T);
    }
}