bzoj 2565: 最长双回文串 manacher

→←

【想说的话】

没有..

【题解】

肯定是先跑一遍manacher

然后就想找到对于每个字符，它作为一个回文串的起点和终点时，回文串最长能为多少

这时候我们发现当一个字符作为终点时，最长的回文串的对称中心一定是最靠前越好

那么我们就像是跑manacher时，从前往后扫，维护一个最右端点，如果找到了右端点大于最右端点的，就暴力地把这一段都计算下

假设我们目前扫到的对称中心为i，i+r[i]大于maxr了，那么就从maxr+1扫到i+r[i]，假设扫到的是j，那么以它为终点的回文串最长为j-i+1

找以一个字符为起点的最长回文串就反过来扫一遍就好了

【代码】

#include<bits/stdc++.h>

using namespace std;

char c[100010];
char s[200020];
int r[200020],Max[200020],ans1[200020],ans2[200020];
int n;

void manacher(){
	int mr=0,num,len=strlen(c);
	r[0]=1;
	for(int i=0; i<len; i++)s[n++]='#',s[n++]=c[i];
	s[n++]='#';
	for(int i=0; i<n; i++){
		if(mr>i)r[i]=min(r[2*num-i],mr-i+1);
		while(i-r[i]>=0 && i+r[i]<n && s[i+r[i]]==s[i-r[i]])r[i]++;
		if(r[i]+i-1>mr)mr=r[i]+i-1,num=i;
	}
}

int main(){
	scanf("%s",c);
	manacher();
	int last=0;
	for(int i=0; i<n; i++){
		if(i+r[i]-1>last){
			for(int j=last+1; j<i+r[i]; j++)if(s[j]!='#')ans1[j]=j-i+1;
			last=i+r[i]-1;
		}
	}
	last=n;
	for(int i=n-1; i>=0; i--){
		if(i-r[i]+1<last){
			for(int j=last-1; j>i-r[i]; j--)if(s[j]!='#')ans2[j]=i-j+1;
			last=i-r[i]+1;
		}
	}
	int ans=0;
	for(int i=1; i<n; i++)if(s[i]!='#')ans=max(ans,ans1[i]+ans2[i+2]);
	printf("%d\n",ans);
	
	return 0;
}