[国家集训队]最长双回文串

传送门

Luogu

题解

考虑建两个回文自动机，一个正串一个反串，然后直接算断点即可。

代码实现

/*
  mail: mleautomaton@foxmail.com
  author: MLEAutoMaton
  This Code is made by MLEAutoMaton
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define int ll
#define REP(a,b,c) for(int a=b;a<=c;a++)
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline int gi(){
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=400010;
int n,a[N],b[N],ans;
char s[N];
struct PAM{
	int last,tot;
	struct node{
		int ff,son[26],len;
	}t[N<<1];
	void init(){last=0;tot=1;t[0].ff=t[1].ff=1;t[1].len=-1;}
	void extend(int c,int n){
		int p=last;
		while(s[n]!=s[n-t[p].len-1])p=t[p].ff;
		if(!t[p].son[c]){
			int k=t[p].ff,np=++tot;t[np].len=t[p].len+2;
			while(s[n]!=s[n-t[k].len-1])k=t[k].ff;
			t[np].ff=t[k].son[c];t[p].son[c]=np;
		}
		last=t[p].son[c];
	}
}P1,P2;
signed main(){
	scanf("%s",s+1);n=strlen(s+1);
	P1.init();P2.init();
	for(int i=1;i<=n;i++){P1.extend(s[i]-'a',i);a[i]=P1.t[P1.last].len;}
	reverse(s+1,s+n+1);
	for(int i=1;i<=n;i++){P2.extend(s[i]-'a',i);b[n-i+1]=P2.t[P2.last].len;}
	for(int i=1;i<n;i++)ans=max(ans,a[i]+b[i+1]);
	printf("%lld
",ans);
	return 0;
}