KMP 讲解
这是 算法第四版 上的 KMP 算法。代码十分简洁，但是十分难懂。在我查了很多资料，想了很久之后，略懂一些。希望能记录下来，用于以后的复习。有的写得不周的地方，多多包涵。
public class KMP
{
private String pat;
private int[][] dfa;
public KMP(String pat) {
// 由模式字符串构造 DFA
this.pat = pat;
int M = pat.length();
int R = 256;
dfa = new int[R][M];
dfa[pat.charAt(0)][0] = 1
for (int X = 0, j = 1; j < M ; j++) {
for (int c = 0; c < R; c++) {
dfa[c][j] = dfa[c][X] //复制匹配失败情况下的值
}
dfa[pat.charAt[j]][j] = j + 1 //设置匹配成功情况下的值
X = dfa[pat.charAt[j]][X] //更新重启状态
}
}
public int search(String txt) {
// 在 txt 上模拟 DFA 的运行
int i, j;
N = txt.length();
M = pat.length();
for (int i = 0, j = 0; i < N && j < M; i++) {
j = dfa[pat.charAt[i]][j];
}
if (j == M) {
return i - M; // 找到匹配（到达模式字符串的结尾）
}else {
return N; // 未找到匹配（到达文本字符串的结尾）
}
}
}KMP 的核心思想是利用已经匹配过的信息来避免重复匹配。
下面看个例子
文本串：A A B A A B A A F A
模式串：A A B A A F
i, j分别代表文本串、模式串的下标
前 t-1+5 次匹配完，第 t-1+6 次匹配
t ⬇
···A A B A A B A A F A
···A A B A A F
⬆
此时 i 与 j 不一样。按照暴力的解法会变成下面这样，重新匹配。
⬇
···A A B A A B A A F A
···A A B A A F
⬆ DFA 构造
那我们可以看到 [t,i) 与 [t,j) 匹配一致，那我们能不能利用这个信息，做点事情，从而快速的移动到正确的位置，减少重复匹配。
由于文本串[t,i) 与 模式串[t,j) 匹配一致，那我们只要研究模式串[t, j) 部分。如果匹配失败，该回退到到哪里，才能保证匹配效率最大化。
也就是说，我们的研究目标变成了，以模式串[t, j) 部分为目标串，除去第一个位置外，找到最佳匹配位置。这样与目标串无关，是模式串自身与自身匹配。我们可以提前制定一张查询表，从而优化算法。
// dfa[256][pat.lenth]
// pat.charAt[0] 取得 模式串(pattern) 下标为 0 字符
dfa[pat.charAt[0]][0] = 1
for (int X = 0, j = 1; j < M ; j++) {
for (int c = 0; c < 256; c++) {
dfa[c][j] = dfa[c][X] //复制匹配失败情况下的值
}
dfa[pat.charAt[j]][j] = j + 1 //设置匹配成功情况下的值
X = dfa[pat.charAt[j]][X] //更新重启状态
}由此我们再来看 KMP 的 dfa 的构造部分。j 为什么是从 1 开始就不难理解了。现在还有几个问题。X 代表什么？ dfa 数组 代表着什么？
dfa 就是上文所说的查询表。给定两个输入，输出 模式串下标 该回退到哪里去。
输入：当前字符和当前状态
输出：下个状态
接下来就是以 以模式串[t, j) ，除去第一个位置外，为目标串，也就是[t+1, j)；以[t, j) 为模式串去匹配，去构造查询表
这里我们用到动态规划的思想。第 j+k 的查询表构造可以由 j+k-1 推导出来。动态规划初始化是 X=0， dfa[pat.charAt[0]][0] = 1。
Next 数组构造
我们可以出，如果能回退到某个状态，那么子串拥有最大公共前后缀。上面 dfa 也是在寻找这个目标。具体可以参考 印度小哥讲解KMP算法
由此引出了子串最大公共前后缀。匹配过的模式串[t...j) 求得。利用子串最大公共前后缀，快速定位。
首先我们先来看 search 部分
我这里的 dfa数组 和视频里的 next 数组会有不同的地方，原理是一样的，后续也会看到如何降维从而构造出视频中的 next 数组。