KMP算法

KMP算法

首先kmp算法有两个字符串，一个目标串s[]，一个模板串p[]

我们需要对模板串进行预处理，创建一个数组ne[i]表示以p[i]为结尾的字符串和前缀相等字符串的最长长度，就是前缀的字符串的长度

1 //预处理
2 char p[N];
3 int ne[N]//ne[i]记录最长相等前缀后缀的长度
4 int n;//n为模板串开始，我们的模板串下表从1开始
5 for(int i=2,j=0;i<=n;i++){
6 while(j>0&&p[j+1]!=p[i]) j=ne[j];//这里1~j与i-j-1~i-1已经匹配，就看j+1和i是否匹配，来看前缀后缀相等长度是否会增加
7 if(p[j+1]==p[i]) j++;//如果匹配长度就加一
8 ne[i]=j;//j就是以i为结尾的后缀和前缀的最长长度

这里i表示后缀的结尾，j表示前缀的结尾，前缀和后缀相等的话就需要1~j和i-j~i匹配

我们这里要求的前缀和后缀都是真子缀，即后缀和前缀不能相等，因此i从2开始而不是1，因为自己和自己永远是匹配的，所以我们一个字符串长度起码是2

然后我们是先判断第i个字符和j+1个字符是否匹配，我们while循环的功能保证了p[i]和p[j+1]是匹配的，这里前面都是已经匹配的，即i-1都是匹配完成的，或者j=0，即前面没有和它匹配的就看这个新增的是否会和它匹配

判断完后if(p[i]==p[j+1])这里有个特殊情况，如果j==0的话p[i]和p[j+1]不一定匹配，即j不一定加一,其余情况长度肯定加一

//模板和目标的匹配
for(int i=1j=0;i<=m;i++){
while(j>0&&s[i]!=p[j+1]) j=ne[j];
if(s[i]==p[j+1]) j++;
if(j==n){//这里表示匹配完成了一个
num++;
j=ne[j];//这里可以直接让j=0
}

最后num就是匹配的字符串个数，这里字符串不重叠