「bzoj2565」最长双回文串 - 回文自动机

题目大意

    输入长度为$n$的串$S$，求$S$的最长双回文子串$T$,即可将$T$分为两部分$X,Y$，（$\left|X\right|,\left|Y\right|\ge1$）且$X$和$Y$都是回文串。

---

题目分析

建立两个回文自动机，一个按照原串建立，一个按照翻转串建立。
枚举位置分别在两个串中查询回文长度，拼起来更新答案。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=100005;

struct Palindsome_Automaton {
	int child[maxn][28];
	int n,size,last,s[maxn],len[maxn],f[maxn],next[maxn];
	Palindsome_Automaton() {
		size=-1;
		newnode(0); //even
		newnode(-1); //odd
		last=n=0;
		s[0]=-1;
		next[0]=next[1]=1;
	}
	int newnode(int v) {
		int now=++size;
		memset(child[now],0,sizeof(child[now]));
		next[now]=0;
		len[now]=v;
		return now;
	}
	void insert(int data,int id) {
		s[++n]=data;
		int p=last;
		while(s[n-len[p]-1]!=s[n])p=next[p];
		if(!child[p][data]) {
			int now=newnode(len[p]+2),q=next[p];
			while(s[n-len[q]-1]!=s[n])q=next[q];
			next[now]=child[q][data];
			child[p][data]=now;
		}
		last=child[p][data];
		f[id]=len[last];
	}
	void build(string s) {
		int tot=0;
		for(auto x:s)insert(x-'a',++tot);
	}
} pam1,pam2;

int ans=0;
string s;

int main() {
	cin>>s;
	int len=s.length();
	pam1.build(s);
	reverse(s.begin(),s.end());
	pam2.build(s);
	for(int i=1; i<len; i++)ans=max(ans,pam1.f[i]+pam2.f[len-i]);
	printf("%d\n",ans);
	return 0;
}