P8112 [Cnoi2021] 符文破译 题解

· · 题解

题意简述

给定两个字符串 t,s，将 s 划分为 n 个子串，使得每一个子串都是字符串 t 的前缀（含 t）。

求满足条件时最小的 n，无满足的情况则输出Fake。

数据范围： |t|,|s|\le 1\times10^7。

思路分析

注：记字符串规模为 n。

考虑到字符串长度如此之大，我们需要一个 O(n) 的算法，因为要求和前缀有着很强的关联性，我们不难想到 KMP 算法，如果没有了解过 KMP 算法，可以先尝试 P3375 【模板】KMP，关于该算法的详细分析，这里就不过多赘述了。

这是一个 KMP 模板的关键操作：

//预处理next数组
for(int i=2,j=0; i<=lt; ++i) {
    while(j&&(t[i]!=t[j+1]))j=nxt[j];
    if(t[i]==t[j+1])++j;
    nxt[i]=j;
}
//进行匹配
for(int i=1,j=0; i<=ls; ++i) {
    while(j&&(j==lt||s[i]!=t[j+1]))j=nxt[j];
    if(s[i]==t[j+1])++j;
}

字符串 s 每匹配成功一次，我们就得到了一个可划分出的子串，也就是说：只要每次尝试匹配后，匹配长度 j 都不为 0，字符串 s 就是可划分的，这样就解决了什么时候输出 Fake 的问题。

那么，怎样求最小划分呢？

其实，只需要尽可能利用已匹配的部分，只有当这次匹配的起点超过上次记录的终点位置时，才进行更新答案。因为当前匹配的终点只会往前推进，所以这样操作可以证明是正确的。

具体看代码：

//匹配部分进行答案更新,x表示上次匹配的终点位置
for(int i=1,j=0,x=0; i<=ls; ++i) {
    while(j&&(j==lt||s[i]!=t[j+1]))j=nxt[j];
    if(s[i]==t[j+1])++j;
    if(j==0){//当匹配失败时，输出Fake
        puts("Fake");
        return 0;
    }
    if(i-j+1>x)++ans,x=i;//本次匹配的起点超过上次的终点时，更新答案和位置,i-j+1即为起点
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int lt,ls,nxt[N],ans;
char t[N],s[N];
int main(){
    ios::sync_with_stdio(0);
    cin>>lt>>ls;
    cin>>t+1,cin>>s+1;
    for(int i=2,j=0;i<=lt;++i){
        while(j&&(t[i]!=t[j+1]))j=nxt[j];
        if(t[i]==t[j+1])++j;
        nxt[i]=j;
    }
    for(int i=1,j=0,x=0;i<=ls;++i){
        while(j&&(j==lt||s[i]!=t[j+1]))j=nxt[j];
        if(s[i]==t[j+1])++j;
        if(j==0)puts("Fake"),exit(0);
        if(i+1>j+x)++ans,x=i;
    }
    cout<<ans;
    return 0;
}

截止文章发布时，本题的题解和提交均没有在时间效率和空间消耗上更优的代码，因此写了这篇题解以增加 RP。