1、前言

2、思路

这道题虽然简单，但是肯定不能用双层 for 循环来做，所以能想到是使用 kmp 来做。

但是 kmp 特别不好理解，特别是 next 数组不知道为何而产生，所以我们需要用状态机的方式来理解。KMP算法的主要思想是提前判断如何重新开始查找，而这种判断只取决于模式字符串本身。所以我们需要针对模式串本身构建状态机。后面的查询操作只是根据 txt 串不断的推进状态机的状态更新，只有状态机到了终态，我们才能肯定完全匹配成功。

3、代码

public class StrStr {

    public int strStr(String haystack, String needle) {
        if(needle == null || needle.length() == 0){
            return 0;
        }
        int M = needle.length();
        int N = haystack.length();

        // 构造模式串 needle 的状态机
        // dp[状态][字符] = 下个状态
        int[][] dp = new int[M][256];

        // base case
        dp[0][needle.charAt(0)] = 1;
        // 影子状态 X 初始为 0
        int x = 0;
        for(int i = 1; i < M; i++){
            for(int c = 0; c < 256; c++){
                dp[i][c] = dp[x][c];
            }
            dp[i][needle.charAt(i)] = i + 1;
            // 更新影子状态
            x = dp[x][needle.charAt(i)];
        }

        // pat 的初始态为 0
        for(int i = 0, j = 0; i < N; i++){
            // 计算 pat 的下一个状态
            j = dp[j][haystack.charAt(i)];

            // 到达终止态，返回结果
            if(j == M){
                return i - M + 1;
            }
        }

        // 没到达终止态，匹配失败
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new StrStr().strStr("", "hh"));
    }
}