数据结构复习局——KPM算法
- 何为KPM？
- 事先规则
- 状态
- 匹配
- dp——状态转移图
- 状态X
- 获得dp数组值
- 看看图再理解下
写在前面：
本文仅为作者个人学习记录，详细具体内容参考自知乎大佬labuladong 👈点击与大佬🤺击剑🤺
话不多说，上代码
public class KMP {private int[][] dp;private String pat;public KMP(String pat) {this.pat = pat;int M = pat.length();// dp定义为：dp[状态][字符] = 下个状态//在相应的状态、字符定位位置的dp，其值指代下一个达到的状态dp = new int[M][256];// 初始化：//只有在状态0处，遇到第一个字符时，dp才会为1进入状态1dp[0][pat.charAt(0)] = 1;// X 初始为状态 0int X = 0;// 构建状态转移图for (int j = 1; j < M; j++) {for (int c = 0; c < 256; c++)dp[j][c] = dp[X][c];//此处j从1开始，找到状态1想要进入状态2时遇到的字符dp[j][pat.charAt(j)] = j + 1;// 更新状态XX = dp[X][pat.charAt(j)];}}public int search(String txt) {int M = pat.length();int N = txt.length();// pat 的初始状态为 0int 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;}
}
何为KPM？
命名来自算法发表团队成员姓名，简写为KPM。
KPM算法与相对于简单匹配算法相比较，更为高效的串的模式匹配算法。
相比于简单匹配算法一步一匹配，一错全回退的不足之处，KPM算法优化了匹配模式串的效率。
本文介绍的KPM不同于课本所讲的，采用二维数组的方式来进行优化。
（不懂简单匹配算法的，还不速速去学~）
事先规则
首先定义一下，方便理解：
pat——模式串，即需要从母串中匹配出的子串，长度M
txt——文本串，被匹配的母串，长度N
所谓KMP算法，即区别于简单模式匹配算法，永不退回TXT指针i，不走回头路。
状态
将母串匹配子串的过程，理解为状态的转换
举个例子：
我们这里有一个pat“ABABC”，它的匹配过程是：先找到“A”，找到“A”后查看下一个字符是否是“B”，再看下一个……一直到从母串中匹配出“ABABC”为止。
这个匹配过程，将其理解为状态的转换：没有匹配到pat的任何一个字符叫做状态0，匹配到一个叫状态1，以此类推，即此处举例的字符串，在状态5时完成匹配。
匹配
理解了什么是状态的转换，那么匹配的过程就可以生动的描述为，状态的转换，从状态0一步一步转换到最终态 pat.length()
这里来定义一个二维数组dp——
dp = int[状态值][字符]；
此处的二维数组中，行值代表当前的状态值，列值代表所匹配到的字符，而被_该行列值所指定的数组值_，即下一个要达到的状态值*。
到了这里，只需要找到dp = 1 - 5的几组转移关系的状态值和字符了，而dp也就成为了一副状态转移图。
那么其实匹配过程的函数就可以写出来了：
public int search(String txt){int M = pat.length();int N = txt.length();//初始状态下，pat状态为0int j = 0;//遍历txt串for(int i = 0; i < N; i++){//状态j，遇到字符txt[i]//若状态j时，遇到字符为匹配字符，则状态推进，即j+1j = dp[j][txt.charAt(i)];//判断一下是否达到终止态，达到终止态则返回匹配开头的索引if(j == M) return i - M + 1;}//循环结束，遍历txt没达到终止态，则匹配失败return -1；
}
dp——状态转移图
上述过程理解之后，显而易见的是，需要根据dp数组的信息，在遍历txt时，来进行匹配，确定在状态几时遇到字符c，需要转换到状态几。
再看一次dp的定义：
dp = int[状态值][字符]；
显然，dp的状态值与字符不成问题，问题是二者定位得到的数组值
- 同样pat是“ABABC”时，当处于状态2，即子串匹配到了“AB”的状态，只有下一个字符匹配到“A”时，才可以从状态2推进至状态3，也就得到：dp[2][‘A’] = 3
AB ABAABABC(2) ABABC(3)
- 同理可得：当处于状态2却遇到了字符“C”时，需要回退到状态0，重新开始匹配：
AB ABCABABC(2) ABABC(0)
- 那么状态回退就一定是回退到0吗？也不尽然——例如👇
ABAB ABABAABABC(4) ABABC(3)
此处的例子中，虽然状态4没有匹配到想要的字符“C”，但匹配到字符“A”时，算法将其退回至状态3，这里又是什么逻辑呢？
状态X
上述例子中，最后一个为什么可以从状态4回退到状态3呢？细心的朋友可能发现在最开始的代码里，定义了一个状态X
int X = 0;
给其初始化值为0，那么这里的状态X，就是匹配状态永远晚一步的状态，何解？
- 现有已知逻辑：状态从0——5（此处5代指最终态），匹配字符个数的增多，伴随状态前进状态数增加
- 从匹配到状态1开始，状态X即有：
-
X = dp[X][txt.charAt(0)]
- 即：X随着状态转变，状态数+1，X随之+1，并记录下转变前状态
- 当状态回退时，即回到X记录的之前的状态：
-
dp[j][c] = dp[X][c];
由此，解释了为什么KMP算法不需要txt指针的回退，pat的不断回退代替了txt指针回退，不断与母串进行匹配比较
获得dp数组值
上述逻辑言明，即可得到dp数组中值究竟何来：
public KMP(String pat){this.pat = pat;int M = pat.length();//dp的值为下一个状态dp = new int[M][256];//初始化:状态0时，遇到pat的第一个字符，状态推进到1dp[0][pat.charAt(0)] = 1;//状态X初始为0int 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;elsedp[j][c] = dp[X][c];}//更新X状态X = dp[X][pat.charAt(j)];
}
至此，二维数组实现KMP算法所有逻辑及代码梳理结束
看看图再理解下
记录学习、爬坑经验
究极小白，欢迎大佬指点！
希望可以帮到你！
