博客

1、KMP算法匹配流程

串的下标从1开始，i从1开始，j从0开始。

2、代码实现

2.1、模式串next数组的生成

next数组就是一个前缀函数数组，可以先了解前缀函数的组成

next数组的生成方式是自己和自己匹配生成的

    for(int j=0,i=2;i<=n;i++){
        while(j&&p[i]!=p[j+1])j=ne[j];//j变小至归零时，停止循环
        if(p[i]==p[j+1])j++;
        ne[i]=j;//先更新j，后给ne赋值
    }

2.2、KMP匹配过程

匹配过程参考匹配流程图

    for(int i=1,j=0;i<=m;i++){
        while(j&&s[i]!=p[j+1])j=ne[j];

        if(s[i]==p[j+1])j++;

        if(j==n){
            printf("%d ",i-n);
            j=ne[j];
        }
    }

2.3、完整代码

#include<iostream>

using namespace std;

const int N = 100010,M=1000010;

char p[N],s[M];
int n,m;
int ne[N];

int main(){
    cin>>n>>p+1>>m>>s+1;
	//next数组
	for(int j=0,i=2;i<=n;i++){
        while(j&&p[i]!=p[j+1])j=ne[j];//j变小至归零时，停止循环
        if(p[i]==p[j+1])j++;
        ne[i]=j;//先更新j，后给ne赋值
    }
    //KMP匹配
    for(int i=1,j=0;i<=m;i++){
        while(j&&s[i]!=p[j+1])j=ne[j];

        if(s[i]==p[j+1])j++;

        if(j==n){
            printf("%d ",i-n);
            j=ne[j];
        }
    }
}

3、问题解决

1、求next中，为什么i从2开始？

因为是模式串自己和自己匹配，所以第一个一定相同，所以只要找到下一个和首字母相同的位置就好。

2、为什么串都要从1开始？

从第一部分的流程图可以观察到，当失配的时候，next数组加上数组之后，下标是从开始的，若串从0开始就会错位。

3、为什么i从1开始，j从0开始？

因为i需要保存的是文本串当前位置，而j保存的是模式串能匹配到的当前位置，下一个位置能不能匹配到是不确定的，所以需要和i错开，当失配的时候能及时返回到next[j]的位置。