P3375

Aryper · 2021-10-20 17:16:21 · 个人记录

【模板】KMP字符串匹配

『あの。青い…』

只记得梦中对那人说了这句话。甚至连自己都不知道下半句是什么。

荒唐到可笑，可笑到可悲。为什么梦中我还在做数论。。。

或许只是太过孤独了罢。

直接贴链接了 从头至尾彻底理解 KMP，以及 浅析KMP，没有看完。。。

基本的思路就是预处理出模式串的 Next_i，表示 [0,i-1] 的最长的相同的前缀和后缀长度（前缀和后缀相同，这个长度最大）。

然后基本就明白了，我们自然是一般地扫过文本串，一般匹配，如果失配了，我们就从模式串的 Next_j 位开始继续匹配，因为前后缀相同所以一定是能匹配上的，但是仍然有失配的可能，所以如果再次失配，我们就到 Next_{Next_j} 继续匹配，以此类推。

那么现在处理如何预处理的问题。其实也是相同的原理，不过是自己与自己匹配。假如说扫到模式串的第 i 位，我们要计算 Next_{i+1} 的值（因为统计对象是 [0,i]），首先令 j=Next_i，显然如果 j 与 i 匹配了，那么 Next_{i+1}=j+1；否则，因为我们失配了，所以 j=Next_j 继续寻找，直到扫完。

正确性无需多言了，现在是时间复杂度的证明。

Quote 一下 rqy 的话：

每次位置指针 i++ 时，失配指针 j 至多增加一次，所以 j 至多增加 len 次，从而至多减少 len 次，所以就是 \Theta(len_N + len_M)=\Theta(N + M) 的。

好巨啊。。。

时间复杂度 O(n+m)。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;

const ll N=1e6;

ll len1,len2;

char s1[N+5],s2[N+5];

ll Next[N+5];

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

void KMP_pre() {
    Next[0]=0;Next[1]=0;
    for(ll i=1;i<len2;i++) {
        ll j=Next[i];
        while(j&&s2[i]!=s2[j]) j=Next[j];
        //注意这里下标的问题
        //因为字符串从 0 开始下标所以要考虑好细节
        //时刻记住 Next 是个长度，只不过变相用作下标
        Next[i+1]=(s2[i]==s2[j])?j+1:0;
    }
}

void KMP() {
    ll j=0;
    for(ll i=0;i<len1;i++) {
        while(j&&s1[i]!=s2[j]) j=Next[j];
        if(s1[i]==s2[j]) j++;
        if(j==len2) writeln(i-len2+2);
    }
}

int main() {

    scanf("%s",s1);scanf("%s",s2);

    len1=strlen(s1);len2=strlen(s2);

    KMP_pre();

    KMP();

    for(ll i=1;i<=len2;i++) {
        write(Next[i]);putchar(' ');
    }

    return 0;
}