KMP算法详解

KMP算法是三位大牛:D.E.Knuth、J.H.Morris和V.R.Pratt同时发明的,主要解决的要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。

现在有一个问题:

给出两个字符串s1和s2,其中s2为s1的子串,求出s2在s1中所有出现的位置

|s1|\le10^5,|s2|\le10^3

Part 0

首先有一个最笨的做法,O(|s1|)去枚举s1的每一位,用s2去判断,这样时间复杂度是O(|s1|*|s2|)的;

Part 1

进入正题。

我们想,如果每次匹配失败,Part0中的算法就要重头再来继续匹配,这是非常不划算的,因为会有以下这样的情况:

a a a c a a c d
a a c d

假设现在正在匹配s1串位置1,第3a\neq c,匹配下一位2

如果我们让匹配s1串位置2的时候直接从第4位开始匹配,岂不美滋滋;

KMP算法就是基于这样的思想;

Part 2

假设我们已经求好了pre[i]表示s2串从1~pre[i]位和i-pre[i]+1~i位是匹配的;

对于s1串某一位i,现在s2串匹配到第j位;

若当前s1[i]==s2[j+1]那么继续匹配下去,反之我们要将j跳到pre[j],直到s1[i]==s2[j+1]j跳到第0位;

for (int i=1,j=0;i<=len1;i++){
    while (j&&S2[j+1]!=S1[i]) j=pre[j];
    if (S2[j+1]==S1[i]) j++;
    if (j==lenb) printf("%d\n",i-lenb+1);
}

Part 3

现在我们看看pre数组怎么求;

发现求pre数组就等同于s2串做一次自匹配,像Part2一样往前跳转即可;

for (int i=2,j=0;i<=len2;i++){
    while (j&&S2[j+1]!=S2[i]) j=pre[j];
    if (S2[j+1]==S2[i]) j++;pre[i]=j;
}

最后的时间复杂度就是O(|s1|+|s2|)

那么KMP就学完辣!!!

最后放上总代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000005
#define maxm 1005
using namespace std;
char S1[maxn],S2[maxm];
int len1,len2,j,pre[maxm];
int main()
{
    scanf("%s",S1+1);scanf("%s",S2+1); //为了方便从1开始
    len1=strlen(S1+1);len2=strlen(S2+1);
    for (int i=2,j=0;i<=len2;i++){ //自匹配
        while (j&&S2[j+1]!=S2[i]) j=pre[j]; //往前跳转
        if (S2[j+1]==S2[i]) j++;pre[i]=j; //求pre的值
    }
    for (int i=1,j=0;i<=len1;i++){
        while (j&&S2[j+1]!=S1[i]) j=pre[j]; //往前跳转
        if (S2[j+1]==S1[i]) j++;
        if (j==len2) printf("%d\n",i-len2+1); //匹配完成
    }
    return 0;
}
0 Comments
Leave a Reply