P8112 [Cnoi2021] 符文破译 题解

题目传送门

思路

先看数据范围，我们发现两个字符串的长度最大会达到 \(5 \times 10^7\)。 这立刻打消了我用暴力的想法。

于是，我选择了用 KMP 模式匹配，这一个能够在线性时间内判定字符串 \(A\) 是否是字符串 \(B\) 的字串，并求出字符串 \(A\) 在字符串 \(B\) 中各次出现的位置。

如果不清楚 KMP 算法是如何实现的，可以看看这个或这个。

我们知道一个字符串 \(A\) 每次往后成功匹配一次，匹配长度就会改变成一个不为 \(0\) 的数，而如果没有匹配成功，则会重新从头开始匹配，匹配长度为 \(0\)。

由此当匹配长度 \(j\) 为 \(0\) 时，无解输出 Fake。

我们也知道每次匹配成功都是 \(A\left[i - j + 1 \sim i\right] = A\left[1 \sim j\right]\)，所以当每次 \(i - j + 1\) 这一个起始点超过了上一次的终止点 \(i\) 时，就可以让划分的段数变小，更新答案。

代码

#include<bits/stdc++.h>
#define int long long
#define MAX 50000005
using namespace std;
int nxt[MAX],lens,lent,ans,tmp;
string s,t;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>lens>>lent>>s>>t;
    s=" "+s;
    t=" "+t;
    for(int i=2,j=0;i<=lens;i++){
        while(j&&s[i]!=s[j+1])j=nxt[j];
        if(s[i]==s[j+1])j++;
        nxt[i]=j;
    }
    for(int i=1,j=0;i<=lent;i++){
        while(j&&(j==lens||t[i]!=s[j+1]))j=nxt[j];
        if(t[i]==s[j+1])j++;
        if(j==0){
            cout<<"Fake\n";
            exit(0);
        }
        if(i-j+1>tmp){//更新答案
            ans++,tmp=i;
        }
    }
    cout<<ans<<'\n';
    return 0;
}