【洛谷P4555】最长双回文串

题目大意：给定一个长度为 N 的字符串 S，求 S 的最长双回文子串的长度，双回文子串定义为是 S 的一个子串，可以分成两个互不相交的回文子串。

题解：利用回文自动机 len 数组的性质，即：len 数组记录的是以每个点 i 字符结尾的，向左可以延伸的，最长回文串的长度。正向遍历一遍串 S，统计出对于每个点向左可以延伸的最长回文长度，再将字符串翻转，统计出向右可以延伸的长度。最后枚举间断点，统计答案即可。

注：增量法回文自动机的插入依赖于字符串下标递增的顺序，因此倒序插入必须将原串转置。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;

char s[maxn];
int n,ans,l[maxn],r[maxn]; 
struct PAM{
	int tot,last,trie[maxn][26],len[maxn],fail[maxn];
	PAM(){tot=1,fail[0]=fail[1]=1,len[1]=-1;}
	int insert(int c,int i){
		int p=last;
		while(s[i-len[p]-1]!=s[i])p=fail[p];
		if(!trie[p][c]){
			int now=++tot,k=fail[p];
			while(s[i-len[k]-1]!=s[i])k=fail[k];
			len[now]=len[p]+2,fail[now]=trie[k][c];
			trie[p][c]=now;
		}
		last=trie[p][c];
		return len[last];
	}
}pam_l,pam_r;

int main(){
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;i++)l[i]=pam_l.insert(s[i]-'a',i);
	reverse(s+1,s+n+1);
	for(int i=1;i<=n;i++)r[n-i+1]=pam_r.insert(s[i]-'a',i);
	for(int i=1;i<n;i++)ans=max(ans,l[i]+r[i+1]);
	printf("%d
",ans);
	return 0;
}