P5410

Aryper · 2021-10-20 19:31:52 · 个人记录

【模板】扩展 KMP（Z 函数）

参考博文 EXKMP。

定义 ext(i) 表示 s[i,sl-1] 与 p 的最长公共前缀。

定义 z(i) 表示 p[i,pl-1] 与 p 的最长公共前缀。

具体算法见博文。

时间复杂度 O(sl+pl)。

代码：

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

const ll N=2e7;

ll pl,sl;

ll z[N+5],ext[N+5];

char p[N+5],s[N+5];

void getZ() {
    z[0]=pl;
    ll now=0;
    while(now+1<pl&&p[now]==p[now+1]) now++;
    z[1]=now;
    ll p0=1;
    for(ll i=2;i<pl;i++) {
        if(i+z[i-p0]<p0+z[p0]) {
            z[i]=z[i-p0];
        }
        else {
            now=p0+z[p0]-i;
            now=max(now,0ll);
            while(now+i<pl&&p[now]==p[now+i]) now++;
            z[i]=now;p0=i;
        }
    }
}

void exkmp() {
    getZ();
    ll now=0;
    while(now<pl&&now<sl&&p[now]==s[now]) now++;
    ext[0]=now;
    ll p0=0;
    for(ll i=1;i<sl;i++) {
        if(i+z[i-p0]<p0+ext[p0]) {
            ext[i]=z[i-p0];
        }
        else {
            now=p0+ext[p0]-i;
            now=max(now,0ll);
            while(now<pl&&now+i<sl&&p[now]==s[now+i]) now++;
            ext[i]=now;p0=i;
        }
    }
}

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');
}

int main() {

    scanf("%s%s",s,p);
    pl=strlen(p);
    sl=strlen(s);

    exkmp();

    ll a0=0,a1=0;
    for(ll i=0;i<pl;i++) {
        a0^=(i+1)*(z[i]+1);
    }
    for(ll i=0;i<sl;i++) {
        a1^=(i+1)*(ext[i]+1);
    }

    writeln(a0);writeln(a1);

    return 0;
}