1.引子
`求子串的在一个长串中的定位操作通常叫做串的模式匹配`
传统的暴力匹配如上图，当遇到一个失配的地方，长串的下一轮的开始匹配的位置就要回溯，
但你要仔细观察的话，就会发现第2 3步其实是多余，直接可以开始第4步开始， 这就引出了我们今天要讲的KMP算法
1.KMP的思路是 在字符失配的情况下，长串不回溯，通过移动模式串(短串)的位置来进行匹配
2.核心是求出一个next数组，数组里面存放的是当前字符失配的情况下，字串需要向右移动的位置
对于如何求next数组以及next数组的推导比较晦涩难懂 我拜读了很多文章后,感觉此篇文章利用块对称性讲解的比较透彻，记录下来供大家学习，传送门 同时我自己也记录一下 加深理解
2.KMP
KMP算法是在模式串字符与主串字符匹配失配时，利用已经匹配的模式串字符子集的最大块对称性，让模式串尽量后移的算法。
这里有3个概念：失配，已经匹配的模式串子集，块对称性
1.失配和隐含信息
在模式串的字符与主串字符比较的过程中，字符相等就是匹配，字符不等就是失配；
隐含信息是，失配之前，都是匹配。
在主串S[0，100]中查找模式串P[0，6]，从下标0开始查找，在下标为5的位置失配，记为P[0，5]失配，则有
P[5]!=S[5]，又有S[0，4]=P[0，4] 则P[0,4]都是匹配的！
2.已经匹配的模式串子集
模式串是P[0，6]，而P[0，4]都是匹配的，所以，已经匹配的模式串子集有
Pcs={ P[0，4]，P[0，3]，P[0，2]，P[0，1]，P[0] }
3.块对称性， 由于比较重要 单独开一栏
2.1 什么是块对称性？
块对称性，就是字符串前缀，后缀重叠；
比如： a b c d a b c
前缀：除了最后一个字母外，所有的前缀子集；
如： a，ab，abc，abcd，abcda，abcdab
后缀：除了第一个字母外，所有的后缀子集;
如： bcdabc，cdabc，dabc，abc，bc，c
这里前缀abc和后缀abc重合
可以把这个重合看做，相对于绿块对称，所以叫它块对称性
块对称有很多种；比如：
2.2 块对称性有什么特点？
特点：拥有块对称性的字符串至少有2块对称重合的的部分；
分析，对称是修饰，重合是关键。而且重合的是前缀和后缀。
模式串如图，如果模式串和主串Str匹配的过程中，在l这失配即P[0，7]失配，你会怎样？
分析，
1，模式串的P[0，6]和主串放入S[0，6]是完全匹配的
2，P[0，6]串是块对称的！
因为P[0，6]刚好有块对称性，我可以把前缀abc移动到后缀abc的位置，然后让d与主串去匹配，这样就利用快对称性了
总结，可以在P[7]失配时，看失配字符的最大前缀P[0，6]是否有块对称性，如果有，我们就可以向右移动模式串，让左边的重合前缀移动到右边的重合后缀，再让模式串和主串比较
2.3 利用最大块对称性？
KMP是在模式串与主串匹配失配时，利用已经匹配的模式串子集的最大块对称性，尽量让模式串右移！这里的利用最大块对称性是什么意思？
这里利用最大块对称性意味着可能发生递归！
KMP算法会预先计算出模式串所有前缀子集中哪些前缀有块对称性，在这些有块对称性的前缀的后一个字符失配时，利用其块对称性；
比如本例中P[0，6]有块对称性，那么在P[0，7]也就是l失配时，
会先利用P[0，6]的块对称性，即P[0，2]和P[4，6]相遇于字符P[3]块对称，
如果不行，会看P[0，2]块对称重合的部分有没有块对称性，
有，就利用；以此类推，一直递归到没有块对称性为止。
2.4 块对称长度的意义-编程
第一次移动中，3是什么？块对称重合长度，也是下次开始比较的位置！
第二次移动中，1是什么？块对称重合长度，也是下次开始比较的位置！
3.next 数组的推导 - 计算块对称性
单独的块对称性是没有意义的，块对称性必须结合上失配，才能利用块对称性！
所以，应该计算出Pattern所有前缀子集失配时的块对称性！放到一个叫next[]数组的地方！
如何计算呢？
next数组是计算失配时的块对称性，
1.当第1个字符失配时，压根就没有前缀后缀的说法，所以有next[0]是不存在块对称性的，记为next[0]=-1；
2.当第2个字符失配时，它的子集只有1个字符，也是没有前缀后缀，没有块对称性，所以记为next[1]=0；
再看图，对于值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，则有next[j] = k。
next[j] = k代表了什么呢？
代表在Pj之前，有长度为k的块对称性，有2个长度为k的重合部分。
总结一下，前提条件如下：
1.next[0]是不存在的，next[1]=0；
2.对于下标值k，已有p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，则有next[j] = k。
next[]数组是从0开始被初始的，如果我们能推导出next[j+1] = 什么，是不是就可以计算出next[]数组？ 是吧
下面来推导next[j+1]
已知：
p0 p1, ..., pk-1 = pj-k pj-k+1, ..., pj-1，==> next[j] = k
如果pk与pj匹配，则有p0 p1, ..., pk-1,pk = pj-k pj-k+1, ..., pj-1pj，==> next[j+1] = k+1;
原来有2个长度为k的对称重合部分，pk与pj匹配后，2个长度为k对称重合的部分又有了1对字符重合，所以有next[j+1]=k+1；
再看图，next[j]=k，当pj失配时，下一次用pk去和主串匹配；所以next[j]的实际意义是，当pj失配时，下一次应该用哪个字符去和主串匹配！！
3. next[ ]数组的值就是当次失配时，下一次匹配的位置！
如果pk与pj不匹配，next[j+1]=?
next[j+1]的实际意义是，p[0，j+1]的pj+1失配时，p[0，j]的块对称重合长度，也是下一次匹配时应该用模式串的哪个字符与主串匹配，那个字符的下标就是next[j+1]。
下一次用哪个字符比较呢？
设a1=p0 p1,...,pk-1，a2=pj-k pj-k+1,...,pj-1；a1==a2
当pk与pj不匹配时，不能用a1替换a2，如图绿叉；
因为a2是离与主串最近的部分，所以这时候应该分析a2是否有块对称性，
如果a2有块对称性，那么a1也有块对称性，如图绿框；
所以，这时应该分析p[0，k]的块对称性，也就是next[k]。
设x1与x2关于绿框对称；x3与x4关于绿框对称；
那么把x1移动到x4的位置，是不是就可以最大利用上；
所以next[j+1]=next[k]；
4. 代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 20 // 存储空间初始分配大小
typedef char String[MAXSIZE + 1];
void get_next(String T, int *next) {
int i,j;
i = 1;
j = 0;
next[1] = 0;
while (i < T[0]) {
if (j == 0 || T[i] == T[j]) {
++i;
++j;
next[i] = j;
} else {
j = next[j];
}
}
}
int Index_KMP(String S, String T, int pos) {
int i = pos;
int j = 1;
int next[255];
get_next(T, next);
//打印next数组
int k = 0;
while (k<=T[0]) {
printf("the nextArr[%d] is %d\n",k,next[k]);
k++;
}
while (i <= S[0] && j <= T[0]) {
if (j == 0 || S[i] == T[j]) {
++i;
++j;
} else {
j = next[j];
}
}
if (j > T[0]) {
return i-T[0];
} else {
return 0;
}
}
#pragma mark 使用
void KMP_Test() {
String s1 = {11,'a','b','c','d','g','a','b','d','e','f','a'};
String p1 = {5,'a','a','a','b','a'};
int index = Index_KMP(s1, p1, 0);
printf("the index is %d\n",index);
}
网友评论