自动搬运

查看原文

来自洛谷，原作者为

	i207M 这个家伙很蠢，什么也没有留下

搬运于2025-08-24 21:48:53，当前版本为作者最后更新于2019-01-03 19:13:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

发这篇题解完全是因为题解里的方法都好麻烦啊...好像是我们暑假考试的题

我们肯定是要KMP求出next数组（以下可能简称nx），然后想办法DP。

我们直接设$f[i]$表示前缀i的答案。

然后我们考虑，$f[i]$只有2种取值：$i,f[nx[i]]$，原因很简单，想覆盖i起码要覆盖$nx[i]$。

什么时候答案才能为$f[nx[i]]$呢，因为前缀i的最后几个字符为$nx[i]$，所以我们最多在后面接上$nx[i]$这么长的字符串，也就是充要条件为存在一个j，使得$f[j]=f[nx[i]],i-nx[i]\le j$

具体实现的话开一个桶即可。

#define N 500005
int n;
int nx[N];
int f[N],h[N];
char s[N];
signed main()
{
#ifdef M207
	freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);
#endif
	scanf("%s",s+1); n=strlen(s+1);
	nx[0]=-1;
	for(ri i=2,j=0; i<=n; ++i)
	{
		while(j!=-1&&s[j+1]!=s[i]) j=nx[j];
		nx[i]=++j;
	}
	f[1]=1;
	for(ri i=2; i<=n; ++i)
	{
		f[i]=i;
		if(h[f[nx[i]]]>=i-nx[i]) f[i]=f[nx[i]];
		h[f[i]]=i;
	}
	out(f[n]);
	return 0;
}