BZOJ [2565: 最长双回文串]

题意：

给出一个字符串$S$，求$S$的最长双回文子串$T$，即可将$T$分为两部分$X$，$Y$，$（|X|,|Y|\ge 1）$ 且$X$和$Y$都是回文串。

题解：

我们知道$len[i]$表示以$i$这个字符结束的最长回文串的长度，然后我们只需要建立两个回文自动机（一个正向一个反向）就可以啦！ 详细细节见代码！

$AC$代码：

#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int MAXN = 5e5+50; struct Palind{ int nxt[MAXN][26],fail[MAXN],len[MAXN],cnt[MAXN]; char str[MAXN]; int sz,lst,sn; void Init(){ fail[0] = fail[1] = 1; len[0] = 0,len[1] = -1; sz = lst = 1; sn = 0; str[0] = '#'; } int Insert(char ch){ str[++sn] = ch; int root = lst; while(str[sn]!=str[sn-len[root]-1]) root = fail[root]; if(!nxt[root][ch-'a']){ len[++sz] = len[root] + 2; int tmp = fail[root]; while(str[sn]!=str[sn-len[tmp]-1]) tmp = fail[tmp]; fail[sz] = nxt[tmp][ch-'a']; nxt[root][ch-'a'] = sz; } lst = nxt[root][ch-'a']; return len[lst]; } }PAM1,PAM2; char s[MAXN]; int lx[MAXN],ly[MAXN]; int main(){ scanf("%s",s+1); int len = strlen(s+1); PAM1.Init(),PAM2.Init(); for(int i=1;i<=len;i++) lx[i] = PAM1.Insert(s[i]); for(int i=len;i>=1;i--) ly[i] = PAM2.Insert(s[i]); int res = 0; for(int i=1;i<=len-1;i++) res = max(res,lx[i]+ly[i+1]); //用原串来解释，lx[i]就是以i为结束的回文串的长度，可以看作向左进行拓展的最长长度 //ly[i+1]就是以i+1为结束的回文串的长度，看作向右拓展的最长长度 cout<<res<<endl; }