自动搬运

查看原文

来自洛谷，原作者为

	Perfound 死在了起跑线，死人一生平安

搬运于2025-08-24 22:04:28，当前版本为作者最后更新于2023-09-26 21:21:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

可以看得出来本题就是求把原串复制一遍后求每个长度为 $n$ 的子串的本质不同回文字串的最大值。

于是可以直接 区间本质不同回文字串。

但是数据范围不行，于是考虑直接维护一个动态回文自动机，可以开头删和尾部加。

对于开头可以和尾部维护最大回文后缀一样维护每个位置开头的最大回文前缀。而删除开头的字符后如果回文树不会变化，那么这个位置开头的最大回文前缀一定在后面出现过。于是可以对于尾部加入的字符暴力跳 $fail$ 修改每个可行的回文后缀的最大出现时间。

因为题目上写明的数据水所以可以过，不过应该可以离线下来用线段树维护。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;char s[3000010];int ed[3000010],pt[3000010];
int t[3000010][26],is[3000010],ln[3000010],to[3000010],idx,n,res,ans;
int find(int p,int i,int x){while(i-ln[p]-1<x||s[i]!=s[i-ln[p]-1])p=to[p];return p;}
int main(){
	scanf("%s",s+1),n=strlen(s+1);
	ln[0]=0,ln[1]=-1,to[0]=1,to[1]=-1,idx=1;
	for(int i=1;i<=n;i++)s[i+n]=s[i]-='a';
	for(int i=1,p=0;i<=(n<<1);i++){
		if(i>n&&i-n+ln[is[i-n]]-1==ed[is[i-n]]){
			t[pt[is[i-n]]][s[i-n]]=0,res--;
			if(is[i-n]==p)p=to[p];
		}
		p=find(p,i,max(1,i-n+1));
		if(!t[p][s[i]]){
			to[++idx]=t[find(to[p],i,max(1,i-n+1))][s[i]],res++;
			ln[idx]=ln[p]+2,t[p][s[i]]=idx,pt[idx]=p;
		}p=t[p][s[i]],ans=max(ans,res);
		for(int q=p;~q;q=to[q])ed[is[i-ln[q]+1]=q]=i;
	}
	cout<<ans;return 0;
}

好像官方正解好像也是O(玄学)的。