解读KMP算法
Hlooog 人气:0
前后断断续续搞了5个月，每次都以为自己懂了， 但是要写的时候都不知从何下手，然后又是各种找博客，看帖子，所以这次试着用自己的语言写一个博客。
首先，KMP算法就是从一个模板字符串（S） 中匹配目标字符串（P）。匹配的话，首先就是想到了暴力匹配，也就是用两个下标表示在S的下标（si） 和 P的下标（pi), 然后进行循环，如果s.chatAt(si)==p.chatAt(pi)
就是si ++， pi++； 如果不相等的话，就需要把si = si - pi + 1, pi = 0; ，然后判断 `pi == p.length()
相等的话，就是匹配成功，可以返回， 不相等就继续。 下面贴一下代码， 图就不画了。
public int violenceMatch(String s, String p){
int sLen = s.length(), pLen = p.length();
int si = 0, pi = 0;
while (si < sLen && pi < pLen) {
if (s.charAt(si) == p.charAt(pi)) {
si++;
pi++;
} else {
si = si - pi + 1;
pi = 0;
}
}
if (pi == pLen) {
return si - pi;
} else {
return -1;
}
}
使用暴力匹配的缺点很明显，就是每次失配（就是s.chatAt(si) != p.chatAt(pi ）的时候，需要把 si 的位置 置为s.chatAt(si)==p.chatAt(pi)开始的点的下一位，这样会出现很多重复无效的匹配。
KMP算法就是把这些重复无效的匹配解决了，具体怎么解决，这个也是KMP算法的精髓（next数组的求解）。 关于next数组的求解，我们稍后说，我们先体会一下 怎么使用KMP算法来进行字符串匹配（如果只想了解next数组是怎么求出来的，可以跳过这部分）， 举个例子，有模式串S: "CDABADABCABADABAB", 目标串 ABADABAB
用目标串推出的next数组是{0,0,1,0,1,2,3,2}(后面会具体讲怎么推出来的)，现在我们开始使用KMP算法进行匹配。
一开是 si = 0， pi = 0。
我们可以看到这个位置不匹配的，然后因为当前pi == 0 所以直接si += 1 pi 不动 进行下一步 此时 si = 1，pi = 0
此时也是不匹配的， 然后重复上一步， 此时 si = 2, pi = 0
当si = 2， pi= 0的时候，s.chatAt(si) == p.chatAt(pi) ，所以此时 si += 1, pi += 1， 重复这样匹配，我们发现在si = 8,pi=6的时候失配了，这是用就需要用到我们的next数组了。
这里先简单说next数组的一样，是当前下标所对应的最长公共前后缀，注意是最长，不是个数，是长度!!! 公共前后缀，都是基于当前下标来说的。举个例子 ABA 这个next数组是 {0 0 1} 对于0下标，没有前后缀， 因为只有1个数， 对于1的下标，前缀是A， 后缀是B，A != B, 所以还是0， 对于2的下标，前缀有 A， AB，后缀有 BA，A，所以值为1 ，后面会有详细的介绍，这里只要分辨出前缀和后缀就可以了。
回到正题， 我们当前位置是失配， 所以需要用到next数组，那么这个next数组在这里有什么用呢？ 我们试想一下，在当前下标失配， 说明我前面的都是可以匹配上的，我们的next数组是保存了最长的公共前后缀，我们是不是可以把失配下标的前一个位置在next数组中对应的最大公共前后缀值来作为目标串（P）移动的距离，因为我当前失配的下标的前一个下标有一定的匹配距离，然后这个下标所对应的前缀是不是可以省略比对，直接移动最长公共前后缀的距离。 这里pi = 6的时候失配， next[6 - 1] = 2， 也就是前缀AB （下标0、1）和 后缀AB（下标4、5），我们是不是可以省略AB的比较，直接从 ABAD的A开始继续匹配。因为对于 pi = 6来说， pi = 4, pi=5都是和S串上可以匹配上，省略pi = 0， pi = 1的比较，直接从pi = 2开始和si= 8 继续比对，所以下标变化是si = 8, pi = next[6 - 1]=2也就是下图：
此时对于si = 8, pi= 2 仍然没有匹配上，然后再次使用next数组， next[2 - 1] = 0，所以有 si = 8, pi = next[2 - 1] = 0
此时还是没有匹配上，但是pi = 0， 所以 si+=1，此时 si = 9, pi = 0
后面下去都是匹配上了。所以可以返回下标。
可能看到这里，你还是疑惑这个next下标为什么要这样用呢？这里总结一下，然后就解释next数组的推导过程。 我们在 失配的时候，就需要移动目标串，问题是移动多少呢？不同于暴力匹配的做法，将 si和pi都一起移动，而是只移动 pi，这个移动的距离，和next数组有关，我们当前失配的位置的前一个位置是可以和S模式串失配前的位置是可以匹配的，所以我们只要移动当前pi的前一个位置的最大公共前后缀距离，然后原本由后缀匹配的字符给前缀匹配（因为知道了最大公共前后缀的距离，所以这部分只是移动而已，不需要再重新的匹配），然后在失配的地方继续进行新的比对。
这里开始讲解一下next的推导。我们在前面提到过，next数组对于当前下标所对应的最长公共前后缀，所以我们从index = 1 开始，因为 0 下标只有1个字符，没有前后缀
对于下标1，我们可以很清楚的看到， 前缀是A， 后缀是B，A != B, 所以next[index] = 0，对下标index = 2进行查看
对于下标2，我们也可以很清楚的看到，前缀是A、AB，后缀是BA,A，只有A == A，所以next[index] = 1,好像到这里还是很简单，我们可以先推出一个公式，p.chatAt(index) == p.chatAt(next[index - 1]) 成立的话 next[index] = next[index - 1] + 1, 不成立的话 next[index] = 0,后面我们就用这个公式进行求解，看下这个公式是否成立，在验证结果之前，我先说一下为什么会得出这样的公式， next数组是保存了最长公共前后缀，这个概念说过很多次了，因为它特别重要。 我们对于当前下标，要想找到最长的公共前后缀，最好的办法就是在前一个下标的最长公共前后缀的基础上+1，这点没有问题吧，所以就有了 p.chatAt(index) == p.chatAt(next[index - 1])。 那么接下来，我们就来验证一下这个公式的正确性了。对于下标 index = 3，
有p.chatAt(3) != p.chatAt(next[3 - 1])所以next[3] = 0，我们也可以看出next[3]确实是0， 继续 index = 4
在index = 4的时候，有 p.chatAt(4) == p.chatAt(next[4 - 1]) 所以next[4] = next[4 - 1] + 1，确实没错，继续index = 5
在next = 5的时候，有p.chatAt(5) == p.chatAt(next[5 - 1]) 所以next[5] = next[5 - 1] + 1,也没有错误 ，继续 index = 6
在next =6 的时候， 有p.chatAt(6) == p.chatAt(next[6 - 1]), 所以next[6] = next[6 - 1] + 1, 也没有错误，继续 index = 7
在next = 7 的时候， 有p.chatAt(7) != p.chatAt(next[7 - 1]), 按照公式，此时的next[7] 应该是0 才对呀，但是我写的是 2，我们可以看一下，确实也是2 因为前缀 AB 和后缀AB相等，所以是2， 但是这是为什么呢？我们可以知道 p.chatAt(7) 确实是不等于 p.chatAt(next[7 - 1])，但是不要忘记，我们的next保存的是最长公共前后缀，next[7 - 1] = 3，说明下标0 、 1、 2和下标4、5、6是一一对应的，所以我们对下标4 和7进行比较，发现不相等，按照一开始的思路，我们会把next[7]设为0， 但是我们可以看一下下标 0、 1、 2 、 3这里，对于下标3 是我们下标7要比较的，但是看一下下标2的位置在next数组是1，这表明了，对于下标2，的最长公共前后缀是1，在求next[3]的时候，我们用p.chatAt(3) 和p.chatAt(next[3 - 1])进行比较，对于现在的下标7， 我们是不是可以把它当成是下标3 呢？ 完全可以，因为下标0、1、2和下标4、5、6一一对应， 下标3 和7 没有匹配上，就可以把下标7 看成是下标3， 此时应该是用 p.chatAt(7) 和 p.chatAt(next[3 - 1]), 对于为什么前面是7 后面是next[3- 1] 而不是next[7 - 1]的，如果用next[7 - 1]了， 是不是就陷入了死循环了？ 其实这里也就是把3的下标当作是7来看待，对于3前面的没有其他影响，所以才是这样的。 那么到了此时，我们可以很清晰的求出next数组，然后结合前面的讲解， 就是一个完整的KMP了。
第一次写博客写了2000+字，花费了一些心血画图，试图用最简单的话来叙述这个算法，但是好像没有做到，有一些东西在我这个层次还没有看到，所以也没有用到最简单的话来叙述完全部，大家能多看几遍，也是可以理解这个算法的精妙之处。最后贴一下完整代码：
package com.hl.solution;
/**
* @author Hl
* @create 2021/3/3 0:18
*/
public class KMP {
public static void main(String[] args) {
KMP kmp = new KMP();
String s = "BBC ABCDAB ABCDABCDABDE";
String p = "12";
int i = kmp.kmpMatch(s, p);
int j = kmp.violenceMatch(s, p);
System.out.println("KMP算法结果： "+i);
System.out.println("暴力匹配结果： " + j);
}
// KMP匹配
public int kmpMatch(String s, String p){
int[] next = getNext(p);
int sLen = s.length(), pLen = p.length();
int sl = 0, pl = 0;
while (sl < sLen) {
if (s.charAt(sl) == p.charAt(pl)) {
sl++;
pl++;
} else if (pl == 0) sl++;
else pl = next[pl - 1];
if (pl == pLen) {
return sl - pl;
}
}
return -1;
}
// 求next数组
public int[] getNext(String p){
int[] next = new int[p.length()];
for (int i = 1; i < p.length(); i++) {
int index = next[i - 1];
while (index > 0 && p.charAt(i) != p.charAt(index)) {
index = next[index - 1];
}
if (p.charAt(i) == p.charAt(index)) {
next[i] = index + 1;
}
}
return next;
}
// 暴力匹配
public int violenceMatch(String s, String p){
int sLen = s.length(), pLen = p.length();
int si = 0, pi = 0;
while (si < sLen && pi < pLen) {
if (s.charAt(si) == p.charAt(pi)) {
si++;
pi++;
} else {
si = si - pi + 1;
pi = 0;
}
}
if (pi == pLen) {
return si - pi;
} else {
return -1;
}
}
}
希望大家都能在我这里得到一些收获，感谢看了这么久........
加载全部内容