一、KMP算法的作用
pat表示模式串，长度为M，txt表示文本串，长度为N。KMP 算法是在txt中查找子串pat，如果存在，返回这个子串的起始索引，否则返回 -1。
很明显，pat中根本没有字符 c，根本没必要回退指针i，暴力解法明显多做了很多不必要的操作。
KMP 算法的不同之处在于，它会花费空间来记录一些信息，在上述情况中就会显得很聪明：
因为 KMP 算法知道字符 b 之前的字符 a 都是匹配的，所以每次只需要比较字符 b 是否被匹配就行了。
KMP 算法永不回退txt的指针i，不走回头路（不会重复扫描txt），而是借助dp数组中储存的信息把pat移到正确的位置继续匹配，时间复杂度只需 O(N)，用空间换时间
二、举例说明：
txt1 = "aaacaaab"
pat = "aaab"
txt2 = "aaaaaaab"
pat = "aaab"
我们的txt不同，但是pat是一样的，所以 KMP 算法使用的dp数组是同一个。
只不过对于txt1的下面这个即将出现的未匹配情况：
dp数组指示pat这样移动：
PS：这个j不要理解为索引，它的含义更准确地说应该是状态（state），所以它会出现这个奇怪的位置，后文会详述。
而对于txt2的下面这个即将出现的未匹配情况：
dp数组指示pat这样移动：
状态机概述
为什么说 KMP 算法和状态机有关呢？是这样的，我们可以认为pat的匹配就是状态的转移。比如当 pat = "ABABC"：
如上图，圆圈内的数字就是状态，状态 0 是起始状态，状态 5（pat.length）是终止状态。开始匹配时pat处于起始状态，一旦转移到终止状态，就说明在txt中找到了pat。
比如说如果当前处于状态 2，就说明字符 "AB" 被匹配：
另外，处于某个状态时，遇到不同的字符，pat状态转移的行为也不同。比如说假设现在匹配到了状态 4，如果遇到字符 A 就应该转移到状态 3，遇到字符 C 就应该转移到状态 5，如果遇到字符 B 就应该转移到状态 0：
具体什么意思呢，举例解释一下。用变量j表示指向当前状态的指针，当前pat匹配到了状态 4：
如果遇到了字符 "A"，根据箭头指示，转移到状态 3 是最聪明的：
如果遇到了字符 "B"，根据箭头指示，只能转移到状态 0（一夜回到解放前）：
如果遇到了字符 "C"，根据箭头指示，应该转移到终止状态 5，这也就意味着匹配完成：
当然了，还可能遇到其他字符，比如 Z，但是显然应该转移到起始状态 0，因为pat中根本都没有字符 Z：
这里为了清晰起见，我们画状态图时就把其他字符转移到状态 0 的箭头省略，只画pat中出现的字符的状态转移：
KMP 算法最关键的步骤就是构造这个状态转移图。要确定状态转移的行为，得明确两个变量，一个是当前的匹配状态，另一个是遇到的字符；确定了这两个变量后，就可以知道这个情况下应该转移到哪个状态。
下面看一下 KMP 算法根据这幅状态转移图匹配字符串txt的过程：
请记住这个 GIF 的匹配过程，这就是 KMP 算法的核心逻辑！
为了描述状态转移图，我们定义一个二维 dp 数组，它的含义如下：
dp[j][c] = next
0 <= j < M，代表当前的状态
0 <= c < 256，代表遇到的字符（ASCII 码）
0 <= next <= M，代表下一个状态
dp[4]['A'] = 3 表示：
当前是状态 4，如果遇到字符 A，
pat 应该转移到状态 3
dp[1]['B'] = 2 表示：
当前是状态 1，如果遇到字符 B，
pat 应该转移到状态 2
根据我们这个 dp 数组的定义和刚才状态转移的过程，我们可以先写出 KMP 算法的 search 函数代码：
public int search(String txt) {
int M = pat.length();
int N = txt.length();
// pat 的初始态为 0
int j = 0;
for (int i = 0; i < N; i++) {
// 当前是状态 j，遇到字符 txt[i]，
// pat 应该转移到哪个状态？
j = dp[j][txt.charAt(i)];
// 如果达到终止态，返回匹配开头的索引
if (j == M) return i - M + 1;
}
// 没到达终止态，匹配失败
return -1;
}三、构建状态转移图
回想刚才说的：要确定状态转移的行为，必须明确两个变量，一个是当前的匹配状态，另一个是遇到的字符，而且我们已经根据这个逻辑确定了dp数组的含义，那么构造dp数组的框架就是这样：
for 0 <= j < M: # 状态
for 0 <= c < 256: # 字符
dp[j][c] = next
这个 next 状态应该怎么求呢？显然，如果遇到的字符c和pat[j]匹配的话，状态就应该向前推进一个，也就是说next = j + 1，我们不妨称这种情况为状态推进：
如果遇到的字符c和pat[j]不匹配的话，状态就要回退（或者原地不动），我们不妨称这种情况为状态重启：
那么，如何得知在哪个状态重启呢？解答这个问题之前，我们再定义一个名字：影子状态（我编的名字），用变量X表示。所谓影子状态，就是和当前状态具有相同的前缀。比如下面这种情况：
当前状态j = 4，其影子状态为X = 2，它们都有相同的前缀 "AB"。因为状态X和状态j存在相同的前缀，所以当状态j准备进行状态重启的时候（遇到的字符c和pat[j]不匹配），可以通过X的状态转移图来获得最近的重启位置。
比如说刚才的情况，如果状态j遇到一个字符 "A"，应该转移到哪里呢？首先状态 4 只有遇到 "C" 才能推进状态，遇到 "A" 显然只能进行状态重启。状态j会把这个字符委托给状态X处理，也就是dp[j]['A'] = dp[X]['A']：
为什么这样可以呢？因为：既然j这边已经确定字符 "A" 无法推进状态，只能回退，而且 KMP 算法就是要尽可能少的回退，以免多余的计算。那么j就可以去问问和自己具有相同前缀的X，如果X遇见 "A" 可以进行「状态推进」，那就转移过去，因为这样回退最少：
当然，如果遇到的字符是 "B"，状态X也不能进行「状态推进」，只能回退，j只要跟着X指引的方向回退就行了：
你也许会问，这个X怎么知道遇到字符 "B" 要回退到状态 0 呢？因为X永远跟在j的身后，状态X如何转移，在之前就已经算出来了。动态规划算法不就是利用过去的结果解决现在的问题吗？
PS：对这里不理解的同学建议读读这篇旧文 动态规划设计之最长递增子序列。
这样，我们就可以细化一下刚才的框架代码：
int X # 影子状态
for 0 <= j < M:
for 0 <= c < 256:
if c == pat[j]:
# 状态推进
dp[j][c] = j + 1
else:
# 状态重启
# 委托 X 计算重启位置
dp[j][c] = dp[X][c]
四、代码实现
如果之前的内容你都能理解，恭喜你，现在就剩下一个问题：影子状态X是如何得到的呢？下面先直接看完整代码吧。
public class KMP {
private int[][] dp;
private String pat;
public KMP(String pat) {
this.pat = pat;
int M = pat.length();
// dp[状态][字符] = 下个状态
dp = new int[M][256];
// base case
dp[0][pat.charAt(0)] = 1;
// 影子状态 X 初始为 0
int X = 0;
// 当前状态 j 从 1 开始
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
dp[j][c] = dp[X][c];
}
// 更新影子状态
X = dp[X][pat.charAt(j)];
}
}
public int search(String txt) {...}
}
先解释一下这一行代码：
// base case
dp[0][pat.charAt(0)] = 1;
这行代码是 base case，只有遇到 pat[0] 这个字符才能使状态从 0 转移到 1，遇到其它字符的话还是停留在状态 0（Java 默认初始化数组全为 0）。
影子状态X是先初始化为 0，然后随着j的前进而不断更新的。下面看看到底应该如何更新影子状态X：
int X = 0;
for (int j = 1; j < M; j++) {
...
// 更新影子状态
// 当前是状态 X，遇到字符 pat[j]，
// pat 应该转移到哪个状态？
X = dp[X][pat.charAt(j)];
}
更新X其实和search函数中更新状态j的过程是非常相似的：
int j = 0;
for (int i = 0; i < N; i++) {
// 当前是状态 j，遇到字符 txt[i]，
// pat 应该转移到哪个状态？
j = dp[j][txt.charAt(i)];
...
}
其中的原理非常微妙，注意代码中 for 循环的变量初始值，可以这样理解：后者是在txt中匹配pat，前者是在pat中匹配pat[1:]，状态X总是落后状态j一个状态，与j具有最长的相同前缀。所以我把X比喻为影子状态，似乎也有一点贴切。
另外，构建 dp 数组是根据 base casedp[0][..]向后推演。这就是我认为 KMP 算法就是一种动态规划算法的原因。
下面来看一下状态转移图的完整构造过程，你就能理解状态X作用之精妙了：
状态转移构造过程
至此，KMP 算法就已经再无奥妙可言了！看下 KMP 算法的完整代码吧：
public class KMP {
private int[][] dp;
private String pat;
public KMP(String pat) {
this.pat = pat;
int M = pat.length();
// dp[状态][字符] = 下个状态
dp = new int[M][256];
// base case
dp[0][pat.charAt(0)] = 1;
// 影子状态 X 初始为 0
int X = 0;
// 构建状态转移图（稍改的更紧凑了）
for (int j = 1; j < M; j++) {
for (int c = 0; c < 256; c++)
dp[j][c] = dp[X][c];
dp[j][pat.charAt(j)] = j + 1;
// 更新影子状态
X = dp[X][pat.charAt(j)];
}
}
public int search(String txt) {
int M = pat.length();
int N = txt.length();
// pat 的初始态为 0
int j = 0;
for (int i = 0; i < N; i++) {
// 计算 pat 的下一个状态
j = dp[j][txt.charAt(i)];
// 到达终止态，返回结果
if (j == M) return i - M + 1;
}
// 没到达终止态，匹配失败
return -1;
}
}
五、本文总结
传统的 KMP 算法是使用一个一维数组next记录前缀信息，实现方法不好理解。本文是使用一个二维数组dp以状态转移的角度解决字符匹配问题，但是空间复杂度仍然是 O(256M) = O(M)。