视频讲解：https://www.bilibili.com/video/av49930100?from=search&seid=6859172222314383143

leetcode的简单kmp题：
https://leetcode-cn.com/problems/implement-strstr/solution/kmp-suan-fa-xiang-jie-by-labuladong/
KMP算法-解决字符串问题 - 图1

为了描述状态转移图，我们定义一个二维 dp 数组，它的含义如下：

  1. dp[j][c] = next
  2. 0 <= j < M，代表当前的状态
  3. 0 <= c < 256，代表遇到的字符（ASCII 码）
  4. 0 <= next <= M，代表下一个状态
  5. dp[4]['A'] = 3 表示：
  6. 当前是状态 4，如果遇到字符 A，
  7. pat 应该转移到状态 3
  8. dp[1]['B'] = 2 表示：
  9. 当前是状态 1，如果遇到字符 B，
  10. pat 应该转移到状态 2

根据我们这个 dp 数组的定义和刚才状态转移的过程，我们可以先写出 KMP 算法的 search 函数代码：

  1. public int search(String txt) {
  2.    int M = pat.length();
  3.    int N = txt.length();
  4.    // pat 的初始态为 0
  5.    int j = 0;
  6.    for (int i = 0; i < N; i++) {
  7.        // 当前是状态 j，遇到字符 txt[i]，
  8.        // pat 应该转移到哪个状态？
  9.        j = dp[j][txt.charAt(i)];
  10.        // 如果达到终止态，返回匹配开头的索引
  11.        if (j == M) return i - M + 1;
  12.    }
  13.    // 没到达终止态，匹配失败
  14.    return -1;
  15. }

构建状态转移图

回想刚才说的：要确定状态转移的行为，必须明确两个变量，一个是当前的匹配状态，另一个是遇到的字符，而且我们已经根据这个逻辑确定了 dp 数组的含义，那么构造 dp 数组的框架就是这样：

  1. for 0 <= j < M: # 状态
  2.    for 0 <= c < 256: # 字符
  3.        dp[j][c] = next

这个 next 状态应该怎么求呢？显然，如果遇到的字符 c 和 pat[j] 匹配的话，状态就应该向前推进一个，也就是说 next = j + 1 。

如果字符 c 和 pat[j] 不匹配的话，状态就要回退（或者原地不动），我们不妨称这种情况为状态重启