Zq's Blog KMP,字符串,算法 KMP算法详解

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$,第$3$位$a\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;
}

发表评论

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