自动搬运

查看原文

来自洛谷，原作者为

	Terrific_Year AFOed on 2023.11.18

搬运于2025-08-24 22:36:07，当前版本为作者最后更新于2023-11-14 14:12:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述

给定两个字符串 $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。