KMP算法浅析
KMP算法简介
KMP算法是有Knuth、Morris、Ptatt三人合作的结果，并使用三人名字的首字母作为该算法的命名，该算法在匹配之前对模式串进行了分析，找出模式串的规律，由此大大提高了每次匹配失败后后移算法的性能，讲模式串匹配的时间复杂度提升到了O(n+m)级别。
对于模式串的分析，需要求出模式串的next数组，next[j]表示了，如果当前位匹配不成功时，模式串的指针需要跳转到的位置，其计算方法和表示含义如下所示：
由以上规则，可以很容易写出一个pattern字符串的next数组，如下示例所示：
| pattern | a | b | a | a | b | c |
|---|---|---|---|---|---|---|
| j | 0 | 1 | 2 | 3 | 4 | 5 |
| next | -1 | 0 | 0 | 1 | 1 | 2 |
注意:这里我们字符串的下标都从0开始。
next数组的求解方法
next数组的求解，可以使用定义的方法进行手动求解。但是算法的实现，则可以通过前一个位置的next数组的值推算出来，这种方法的证明不在此处给出，近给出算法的代码实现：
void GetNext(const string &pattern,vector<int> &nextofpattern){ //获取next数组
int sizeofpattern=pattern.size();
nextofpattern.resize(sizeofpattern); //初始化next数组的空间大小
nextofpattern[0]=-1; //next[0]为-1
int i=0,j=-1; //初始化i和j，通过i遍历以计算每个位置的next数值，其中每次通过i的当前信息，推算i+1位置的next值，所以循环到下标size-2处
while(i<sizeofpattern-1){ //j表示了一个最长相同前后缀的长度，
if(j==-1||pattern[i]==pattern[j]){ //如果j已经到达边界，即需要从模式串的头开始匹配（最长相同前后缀长度为0），则此处的next值为0，即要回到模式串的0号位
++i;++j;
nextofpattern[i]=j; //根据当前位置i推算下一个位置(i+1)的next值，如果当前位置i存在更长相同前后缀，则下一个位置(i+1)失配时
} //回到模式串当前最长前后缀的下一个位置(由于下标从0开始，所以下一个位置就是最长前缀的长度)即j+1
else j=nextofpattern[j]; //如果当前位置i无法在next[i]的基础上增长最长前后缀，则j缩短一些
}
}KMP算法的实现
有了next数组之后，则可以使用KMP算法进行匹配，KMP算法的思想是：如果当前位匹配，则文本串和模式串的指针同时后移；如果当前位不匹配，文本串指针不动，匹配串的指针移动到next[j]的位置，继续匹配；直至模式串指针走完匹配完成或者文本串指针走完未完成匹配。其算法的代码实现如下：
int KMP(const string &str,const string &pattern,int pos){ //KMP算法，str为主串，pattern为模式串，pos为查找的起始位置。
vector<int> next;
GetNext(pattern,next); //计算next数组
int i=pos,j=0; //i为查找的起始位置，j为模式串的指针，初始化为0
int sizeofstr=str.size(),sizeofpattern=pattern.size();
while(i<sizeofstr&&j<sizeofpattern){ //当没有匹配完时
if(j==-1||str[i]==pattern[j]){ //如果j=-1表示必须从头开始匹配（刚好j+1变成0，i+1从下一个新的主串位置开始），或者当前位置匹配时，指针都加一
++i;++j;
}
else j=next[j]; //失配时j指针回溯
}
if(j==sizeofpattern) return i-sizeofpattern; //找到时返回模式串出现的起始位置
else return -1; //否则返回-1表示为找到
}KMP算法测试
我们调用KMP算法对其实现进行测试，并检查求解next数组的函数是否工作正常，添加相应的头文件之后，使用以下的代码进行测试：
#include<bits/stdc++.h>
using namespace std;
void GetNext(const string &pattern,vector<int> &nextofpattern);
int KMP(const string &str,const string &pattern,int pos);
int main(void){
string test="abaabc"; //测试模式串
vector<int> next;
GetNext(test,next);
for(int i=0;i<next.size();i++){ //输出next数组
if(i) putchar(' ');
cout<<next[i];
}
cout<<endl;
string str="aaaabaaabaabaabcaabac"; //KMP匹配测试
cout<<"Pos of "<<test<<" in the string "<<str<<" is "<<KMP(str,test,0);
return 0;
}
//补充上Getnext和KMP的代码实现最终的输出如下：
-1 0 0 1 1 2
Pos of abaabc in the string aaaabaaabaabaabcaabac is 10手动求解next数组
对于一串字符，我们先对每个位置求解出其最长相同前后缀长度，但是不能等于整个串的长度，然后将求解到的序列右移一位，0号位补上-1便是下标从0开始的next数组，然后在此基础上每一个数字都加一，获得下标从1开始的next数组。
示例如下：模式串abaabc
//每个位置的最长前后缀长度
a 0
ab 0
aba 1
abaa 1
abaab 2
abaabc 0
//得到一组序列
0 0 1 1 2 0序列右移一位,0号位补-1得到下标从0开始的next数组：
-1 0 0 1 1 2上述序列每一个数字都加一，得到下标从1开始的next数组：
0 1 1 2 2 3
Comments | NOTHING