KMP算法详解

KMP算法详解

我们可以知道,对于两个字符串,最笨的匹配方法就是枚举第一个串的起点,然后第二个串去匹配。

for(int i=0;i<Lena-Lenb+1;i++)
for(int j=0;j<Lenb;j++)
if(a[i+j]!=b[j]) return 0;
return 1;

这种笨蛋的时间复杂度是O(Lena * Lenb)的,效率十分低。

所以就有dalao想出了一个叫看毛片哦不KMP的算法。

简单讲一下想法,对于每个i点,如果当前匹配,那么就继续匹配,否则,b串整体右移,从上一次匹配的地方继续匹配。

比如说:


asdfasdfasdas asdfasdas

我们匹配到第8个位置时,上下不匹配了,那么我们就将b整体右移,变成:


asdfasdfasdas asdfasdas

然后问题就变成了如何快速求出右移后的这个匹配位。

我们会发现只于b有关,而且我们要保证,b右移后,之前位全部匹配。

我们观察以上给出的数据,如果从i能跳到j(j\le i),那么[1,j-1]==[i-j,i-1],否则当匹配a串时,从i跳到j之后,之前就会出现不匹配现象。

有点难说,总之,我们要使i能跳到j,必须[1,j-1]==[i-j,i-1]。

所以可以在自匹配过程中实现:

//洛谷P3375
#include<cstdio>
#include<cstring>
using namespace std;
int n,pre[1000005];
char a[1000005],b[1000005];
int main(){
    #ifndef ONLINE_JUDGE
    freopen("P3375.in","r",stdin);
    freopen("P3375.out","w",stdout);
    #endif
    scanf("%s%s",a,b);
    int Len1=strlen(a),Len2=strlen(b);
    for(int i=1,j=0;i<Len2;i++){//自匹配
        while(j&&b[i]!=b[j]) j=pre[j];//不满足往前跳
        pre[i+1]=(b[i]==b[j]?++j:0);
    }
    for(int i=0,j=0;i<Len1;i++){//与A匹配
        while(j&&a[i]!=b[j]) j=pre[j];//不满足往前跳
        if(a[i]==b[j]) j++;//满足继续匹配
        if(j==Len2) printf("%d\n",i-Len2+2);//找到一个匹配
    }
    for(int i=1;i<=Len2;i++) printf(i==Len2?"%d\n":"%d ",pre[i]);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部