? Java学习：Java从入门到精通总结
? Spring系列推荐：Spring源码解析
? 最近更新：2021年12月13日
? 个人简介：通信工程本硕?、阿里新晋猿同学?。我的故事充满机遇、挑战与翻盘，欢迎关注作者来共饮一杯鸡汤
? 点赞 ? 收藏 ⭐留言 ? 都是我最大的动力！
KMP 算法（Knuth-Morris-Pratt 算法）是一个著名的字符串匹配算法，效率很高，说实话，有点复杂。
这种高级且常用的算法经常会在各种竞赛 / 面试场景中出现，先给大家说一个真实的例子吧，在我当初校招面试华为sp时，面试官就让我当场写一个KMP算法，大致的题目如下：
这个算法是一个比较奇葩的存在，业内流行一句话，当你第一遍没学会掌握kmp时，之后再看就会耗费成倍的精力。不幸的是我第一遍没掌握这个算法，所以当时我是直接把模板给背诵了下来，以一种非正常的方式通过了面试。
之后复盘环节偶然看到了东哥（公众号labuladong）使用动态规划的思路给出的解析，顿感豁然开朗，把之前非常诡异的next数组定义给丢掉了，二维数组的解法不禁让我直呼内行，先整理如下，祝各位蓝桥杯顺利~
约定：pat表示模式串，长度为M，txt表示文本串，长度N为N。KMP 算法是在txt中查找子串pat，如果存在，返回这个子串的起始索引，否则返回 -1。
目前大部分的解析应该是：对pat进行一顿操作之后生成一个next数组，再利用next数组的数据去一顿操作来匹配txt。next数组和txt、pat的前缀后缀有关，很难理解，理解了可能也忘的比较快。我么可以用一个二维数组来减少代码长度，提高可解释性。
1 概述
普通字符串匹配可以用暴力破解来写，具体思路是：从txt起始索引0开始匹配pat，匹配上了则返回起始索引，匹配不上则再从txt索引1处开始匹配，以此类推…
KMP 算法的不同之处在于，它会花费空间来记录一些信息，在上述情况中就会显得很聪明。由于pat中根本不存在c字符，所以可以直接跳过这个字符：
KMP 算法则不会重复扫描txt，而是借助next数组中储存的信息把pat移到正确的位置继续匹配，用空间换时间。
传统的KMP算法框架如下：
// KMP算法主体逻辑。str是主串，pattern是模式串
public static int kmp(String str, String pattern) {
//预处理，生成next数组
int[] next = getNexts(pattern);
int j = 0;
//主循环，遍历主串字符
for (int i = 0; i < str.length(); i++) {
while (j > 0 && str.charAt(i) != pattern.charAt(j)) {
//遇到坏字符时，查询next数组并改变模式串的起点
j = next[j];
}
if (str.charAt(i) == pattern.charAt(j)) {
j++;
}
if (j == pattern.length()) {
//匹配成功，返回下标
return i - pattern.length() + 1;
}
}
return -1;
}
// 生成Next数组
private static int[] getNexts(String pattern) {
int[] next = new int[pattern.length()];
int j = 0;
for (int i=2; i<pattern.length(); i++) {
while (j != 0 && pattern.charAt(j) != pattern.charAt(i-1)) {
//从next[i+1]的求解回溯到 next[j]
j = next[j];
}
if (pattern.charAt(j) == pattern.charAt(i-1)) {
j++;
}
next[i] = j;
}
return next;
}
public static void main(String[] args) {
String str = "ATGTGAGCTGGTGTGTGCFAA";
String pattern = "GTGTGCF";
int index = kmp(str, pattern);
System.out.println("首次出现位置：" + index);
}
我们可以看到，KMP 算法的难点在于如何计算next数组中的信息？如何根据这些信息快速的移动pat的位置？
首先需要明确一点：计算这个数组，只和pat有关。这样的话KMP算法框架可以如下：
public class KMP {
private int[][] dp;
private String pat;
public KMP(String pat) {
this.pat = pat;
// 通过 pat 构建 dp 数组
// 需要 O(M) 时间
}
public int search(String txt) {
// 借助 dp 数组去匹配 txt
// 需要 O(N) 时间
}
}
这样，当我们需要用同一 pat 去匹配不同txt时，就不需要浪费时间构造dp数组了：
KMP kmp = new KMP("aaab");
int pos1 = kmp.search("aaacaaab"); //4
int pos2 = kmp.search("aaaaaaab"); //4
2 状态机
我们可以认为 pat 的匹配就是状态的转移。比如当 pat = "ABABC"时：
圆圈内的数字就是状态，状态 0 是起始状态，状态 5是终止状态。开始匹配时 pat 处于起始状态，一旦转移到终止状态，就说明在txt中找到了pat。如果当前处于状态 2，则说明字符 “AB” 被匹配：
处于某个状态时，遇到不同的字符，pat 状态转移的行为也不同。假设现在匹配到了状态 4，如果遇到字符 A 就应该转移到状态 3，遇到字符 C 就应该转移到状态 5，如果遇到字符 B 就应该转移到状态 0：
具体来说，当前 pat 匹配到了状态 4：
如果遇到了字符 “A”，根据箭头指示，转移到状态 3 ：
如果遇到了字符 “B”，根据箭头指示，转移到状态 0：
如果遇到了字符 “C”，根据箭头指示，转移到终止状态 5，意味着匹配完成：
最终的转移状态图可以画成如下的样子：
构造这个状态转移图，需要两个变量，一个是当前的匹配状态，另一个是遇到的字符；确定了这两个变量后，就可以知道这个情况下应该转移到哪个状态。
如果已经获得了这张转移图，字符串的匹配过程就如下所示：
为了描述状态转移图，我们定义一个二维 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;
}
3 生成状态转移图
3.1 基本框架
“要确定状态转移图，必须明确两个变量，一个是当前的状态，另一个是遇到的字符”。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”。所以当状态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永远跟在j的身后，状态X如何转移，在之前就已经算出来了(动态规划 或者 递归的思想)
因此我们可以优化刚刚的计算dp数组的代码：
// 影子状态
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];
}
}
}
3.2 生成影子状态
总体框架如下：
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) {...}
}
其中的初始状态：
dp[0][pat.charAt(0)] = 1;
只有遇到 pat[0] 这个字符才能使状态从 0 转移到 1，遇到其它字符的话还是停留在状态 0（Java 默认初始化数组全为 0）。
影子状态X是先初始化为 0，然后随着j的前进而不断更新的。
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:length]，状态X总是落后状态j一个状态，与j具有最长的相同前缀。
完整过程：
4 完整代码
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) {
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;
}
}
核心代码是两个函数中 for 循环的部分
5 总结
在pat匹配txt的过程中，只要明确了**「当前处在哪个状态」和「遇到的字符是什么」**这两个问题，就可以确定应该转移到哪个状态。
dp数组的含义：
dp[j][c] = next：当前是状态j，遇到了字符c，应该转移到状态next。
明确了其含义，就可以很容易写出 search 函数的代码。
对于如何构建这个dp数组，需要一个辅助状态X。在构建当前状态j的转移方向时，只有字符pat[j]才能使状态推进（dp[j][pat[j]] = j+1）；而对于其他字符只能进行状态回退，应该去请教状态X应该回退到哪里（dp[j][other] = dp[X][other]，其中other是除了pat[j]之外所有字符）。
我们把X初始化为 0，并且随着j的前进进行更新，更新的方式和 search 过程更新j的过程非常相似（X = dp[X][pat[j]]）。
还没有评论，来说两句吧...