本题$zyys$啊！～
很容易想到$manacher$，于是先打个板子看看，处理出以$i$为中心的最长回文半径$p[i]$后，就断思路了。
我首先想到的是，在每次更新$p[i]$后，分别处理出以$i$为中心的半径$p[i]$内，每个位置为开头和结尾的最长回文子串长度($manacher$结束后直接枚举断点就可以得到答案)，但是这样强行又将复杂度拉到了$O(n^2)$。于是，开始断线～
后面看看巨佬们的思路，豁然**，我是真的蠢啊～
其实，将我开始的思路修改一下即可：
我们维护最长回文半径$p[i]$的同时，再分别维护两个东西，以$i$为结尾的最长回文子串的长度$ll[i]$，和以$i$为开头的最长回文子串的长度$rr[i]$。
那么很显然，因为以$i$为中心的最长回文子串长度为$p[i]-1$，所以每次更新$p[i]$后，我们只需处理出当前这个回文子串的左右边界(中间的每个点的$ll[i],rr[i]$可以在$manacher$结束后$O(n)$处理出)，则$ll[i+p[i]-1]=max(ll[i+p[i]-1],p[i]-1)$(更新以$i+p[i]-1$为结尾的最长回文长度)，同理$rr[i-p[i]+1]=max(rr[i-p[i]+1],p[i]-1)$。
跑完$manacher$后，我们$O(n)$递推出每个'#'为断点的$ll[i]$和$rr[i]$，其中$rr[i]$因为是$i$结尾的回文长度，所以直接顺推，每往后移一位，最长回文子串长度$-2$，于是$rr[i]=max(rr[i],rr[i-2]-2)$($i-2$是上一个'#'位置)，同理$ll[i]$直接逆推，类似地$ll[i]=max(ll[i],ll[i+2]-2)$。
最后枚举每个'#'为断点，更新$ans$就$OK$了。
$\quad\;\;$欢迎来踩博客：five20（蒟蒻写题解不易，转载请注明出处～万分感谢！）
#include<bits/stdc++.h>
#define For(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define Bor(i,a,b,c) for(int (i)=(b);(i)>=(a);(i)-=(c))
#define Min(a,b) ((a)>(b)?(b):(a))
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=200050;
int p[N],ll[N],ans,rr[N],mx,id,cnt;
char s[N],t[N];
int main(){
scanf("%s",t);
int len=strlen(t);
s[++cnt]='$',s[++cnt]='#';
For(i,0,len-1,1)s[++cnt]=t[i],s[++cnt]='#';
s[++cnt]='\0';
For(i,1,cnt,1){
if(i<mx)p[i]=Min(p[id*2-i],mx-i);
else p[i]=1;
while(s[i-p[i]]==s[i+p[i]])p[i]++;
if(mx<i+p[i])id=i,mx=i+p[i];
ll[i+p[i]-1]=Max(ll[i+p[i]-1],p[i]-1);
rr[i-p[i]+1]=Max(rr[i-p[i]+1],p[i]-1);
}
For(i,2,cnt,2)rr[i]=Max(rr[i],rr[i-2]-2);
Bor(i,2,cnt,2)ll[i]=Max(ll[i],ll[i+2]-2);
For(i,2,cnt,2)if(rr[i]&&ll[i])ans=Max(ans,ll[i]+rr[i]);
cout<<ans;
return 0;
}顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为abc，逆序为cba，不相同）。
输入长度为$n$的串$S$,求$S$的最长双回文子串$T$ ,即可将$T$分为两部分$X$,$Y$,
$($|X|$,$|Y|$\geq$1)且 $X$ 和 $Y$ 都是回文串。
首先给出双回文串定义:
双回文串$A$是指一个可以被拆分成两个部分(B和C)的字符串 $A=B+C$, 且$B$和$C$都是回文串的串, A自己本身可以不是回文串.
看到回文很容易想到$manacher$算法
其实正解就是manacher (⊙o⊙)…
我相信大家都理解如何去处理字符串的奇偶,所以不再赘述~~
如果不会$manacher$还是先去敲板子-->manacher
因为双回文串是可以拼接得到的,
所以我们可以预先处理出来数组$RL[i]$
(即代表以$i$为对称轴的最大回文半径)
然后我们可以定义这么两个东西
1:$l[i]$代表$i$位置所在回文串中中心位置最左端的位置
2:$r[i]$代表$i$位置所在回文串中中心位置最右端的位置
我们可以算出来这两个个东西。
因此通过左右拼接就可以得到我们的双回文串了
2018.09.29.
感谢_ConveX指出一个天大的错误.
1.修改了$l$数组与$r$数组的定义.
2.并修改了部分代码,大家看着应该会舒服些
(可能排版不太好,请揍我谅解)
------------------ 代码------------------
#include<bits/stdc++.h>
#define IL inline
#define RI register int
#define N 100010
using namespace std;
char s[N<<1],ch[N];
int MaxRight,center,len;
int RL[N<<1],l[N<<1],r[N<<1];
int pos,ans;
int main()
{
cin>>ch;
len=strlen(ch);
for(RI i=0;i<len;i++)s[2*i+1]=ch[i];
len=2*len+1;//这里不要忘记变化长度！
RL[0]=1;
for(RI i=1;i<len;i++)
{
if(i<=MaxRight)
RL[i]=min(MaxRight-i,RL[2*center-i]);
else
RL[i]=1;
while(i-RL[i]>=0&&RL[i]+i<len&&s[i+RL[i]]==s[i-RL[i]])
++RL[i];
if(i+RL[i]-1>MaxRight)
MaxRight=i+RL[i]-1,center=i;//注意更新操作
}
for(RI i=0;i<len;i++)
for(;pos<=i+RL[i]-1;pos++)
l[pos]=i;//概念和上面讲的一样
pos=len;
for(RI i=len-1;i>=0;i--)
for(;pos>=i-RL[i]+1;pos--)
r[pos]=i;//概念同上面讲的一样
for(RI i=0;i<len;i++)
ans=max(ans,r[i]-l[i]);//为了保险 ,貌似可以直接减 emmm
cout<<ans;
}如果哪里写的不好 请私信我emmm
回文自动机裸题。
分别建两个回文自动机，一个是正序，一个是倒序，然后通过自动机得出最长回文长度，接着枚举切割点就好了。
2018.12.15update：之前忘记考虑不切割的情况，那只要不枚举$n$为切割点就好了。
code：
//2018.11.21 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline int read(){
res s=0;
bool w=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return w?-s:s;
}
inline void _swap(res &x,res &y){
x^=y^=x^=y;
}
inline int _abs(const res &x){
return x>0?x:-x;
}
inline int _max(const res &x,const res &y){
return x>y?x:y;
}
inline int _min(const res &x,const res &y){
return x<y?x:y;
}
const int N=1e5+10;
namespace MAIN{
int n;
int a[N],b[N];
struct PAM{
struct Pam{
int vis[26],len,fail;
}pam[N];
int las,cnt;
PAM() {pam[1].fail=pam[0].fail=1,pam[cnt=1].len=-1;}
inline void extend(const res &x,const res &id,char *str){
res p=las;
for(;str[id-pam[p].len-1]!=str[id];p=pam[p].fail);
if(!pam[p].vis[x]){
res np=++cnt,q=pam[p].fail;
for(;str[id-pam[q].len-1]!=str[id];q=pam[q].fail);
pam[np].fail=pam[q].vis[x],pam[p].vis[x]=np,pam[np].len=pam[p].len+2;
}
las=pam[p].vis[x];
}
}A,B;
char str[N];
int ans;
inline void MAIN(){
scanf("%s",str+1);
n=strlen(str+1);
for(res i=1;i<=n;i++)A.extend(str[i]-'a',i,str),a[i]=A.pam[A.las].len;
reverse(str+1,str+n+1);
for(res i=1;i<=n;i++)B.extend(str[i]-'a',i,str),b[n-i+1]=B.pam[B.las].len;
for(res i=1;i<n;i++)ans=_max(a[i]+b[i+1],ans);
printf("%d\n",ans);
}
}
int main(){
MAIN::MAIN();
return 0;
}下午刚学了 $Manacher$ ，做到这题。
然后对于大佬们的题解做一个更为详细的补充说明，
主要针对自己的一些疑惑，以及不理解的地方做了详尽的诠释
顺手就全写代码里了！有哪里讲的不清楚可以问窝(虽然我很弱
#include <bits/stdc++.h>
#define ll long long
#define space putchar(' ')
#define endl putchar('\n')
#define debug puts("------------------------")
using namespace std;
inline void read(int &a) {a = 0; int c = getchar(), b = 1; while (c > '9' || c < '0') {if (c == '-')b = -1; c = getchar();} while (c >= '0' && c <= '9') a = (a << 3) + (a << 1) + c - 48, c = getchar(); a *= b; }
inline int Rem() {int a = 0, c = getchar(), b = 1; while (c > '9' || c < '0') {if (c == '-')b = -1; c = getchar();} while (c >= '0' && c <= '9') a = (a << 3) + (a << 1) + c - 48, c = getchar(); return a *= b; }
inline void write(int x) {if (x > 9)write(x / 10); putchar('0' + x % 10);}
inline void W(int x) {if (x < 0) {putchar('-'), x = -x;} write(x);}
/**/
const int N = 11000005;
char a[N], s[N << 1];
int n, hw[N << 1], ans, l[N << 1], r[N << 1];
/**/
void Pre()//非常模板的插入
{
s[0] = '#';
s[1] = '$';
int cnt = 1;
for (int i = 1; i <= n; i++)
{
s[++cnt] = a[i];
s[++cnt] = '$';
}
n = (n << 1) + 2;
s[n] = '~';
}
void work()//同样非常模板的Manacher
{
int mr = 0, mid;
for (int i = 1; i <= n; i++)
{
if (i < mr) hw[i] = min(hw[(mid << 1) - i], mr - i);
else hw[i] = 1;
while (s[i + hw[i]] == s[i - hw[i]]) ++hw[i];
if (hw[i] + i > mr) mr = hw[i] + i, mid = i;
/**
* l[i]表示以i为左端点的最长的回文串
* r[i]表示以i为右端点的最长的回文串
*
* 对于蒟蒻(我)来讲有点抽象所以我们举一个生动的栗子：
*
* 首先，字符串为ababaccd
*
* 0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17
* 插入后变成 #|$|a|$|b|$|a|$|b|$|a |$ |c |$ |c |$ |d |~
*
* 显然i = 4时,hw[4] = 4
* L = 7 = i + hw[4]-1;
* R = 1 = i-hw[4]+1;
* 回文串实际长度=hw[4]-1;
* 所以转移就是: l[i+hw[i]-1]=max(l[i+hw[i]-1],hw[i]-1);
* r[i-hw[i]+1]=max(r[i-hw[i]+1],hw[i]-1);
*
*/
r[i + hw[i] - 1] = max(r[i + hw[i] - 1], hw[i] - 1);
l[i - hw[i] + 1] = max(l[i - hw[i] + 1], hw[i] - 1);
}
}
int main()
{
scanf("%s", a + 1);
n = strlen(a + 1);
Pre();
work();
/**
* 又因为两块不能重叠，所以我们选择'$'作为断点进行枚举
*
* 那么先提出一个困扰蒟蒻我的问题：
*
* Q: 上面不是已经求过了吗，为什么还要递推呢？
*
* A: 上面求出的每个l[i]和r[i]都是在i最大的情况下求的
*
* eg:0|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17
* #|$|a|$|b|$|a|$|b|$|a |$ |c |$ |c |$ |d |~
*
* l[3]求出来的是0,但很明显bab是一个回文,l[3]应该等于3
* 这是因为我们在i=6时,hw[i]=6,只更新了l[1]和r[11],因为bab不是i=6的最长回文串所以没有更新
*
* 这时就需要递推把前面的转移过来了：
*
* bab 比 ababa 短两个字符。
* 每一个回文串向后挪动一个 都会少两个字符,所以：
* l[i] = max(l[i], l[i - 2] - 2);
* r[i] = max(r[i], r[i + 2] - 2);
* 我们枚举的是'$'的位置，所以l[i]正推由前一个'$'的位置转移来,r[i]逆推由后面的'$'转移来，每次都会-2回文串长度
*
*/
for (int i = n; i >= 1; i -= 2) r[i] = max(r[i], r[i + 2] - 2);
for (int i = 1; i <= n; i += 2) l[i] = max(l[i], l[i - 2] - 2);
for (int i = 1; i <= n; i += 2) if (r[i] && l[i]) ans = max(ans, l[i] + r[i]);
W(ans);
return 0;
}题意：求字符串的最长子串$S$满足可以分为$X,Y$，使得$X,Y$都是回文串。
设$l[i],r[i]$分别为以第$i$个字符为开头（结尾）的回文子串最长可以，则$ans=\max_{i=0}^{n-2}(r[i]+l[i+1])$.
至于求$l,r$，我们使用回文树把正序和反序都做一遍，每次把这个节点代表的回文子串的长度返回就可以了。
至于manacher，...那是什么神仙东西（大雾
#include<cstdio>
#include<cstring>
#include<algorithm>
#define Rint register int
using namespace std;
const int N = 100003;
struct Palindrome_Automaton {
int ch[N][26], fail[N], cnt[N], len[N], S[N], n, p, last;
inline int newnode(int l){
for(Rint i = 0;i < 26;i ++)
ch[p][i] = 0;
cnt[p] = 0;
len[p] = l;
return p ++;
}
inline void init(){
p = 0;
newnode(0); newnode(-1);
n = last = 0;
S[n] = -1;
fail[0] = 1;
}
inline int getfail(int x){
while(S[n - len[x] - 1] != S[n]) x = fail[x];
return x;
}
inline int insert(int c){
S[++ n] = c;
int cur = getfail(last);
if(!ch[cur][c]){
int now = newnode(len[cur] + 2);
fail[now] = ch[getfail(fail[cur])][c];
ch[cur][c] = now;
}
last = ch[cur][c];
cnt[last] ++;
return len[last];
}
} pa;
int n, l[N], ans;
char str[N];
int main(){
scanf("%s", str);
n = strlen(str);
pa.init();
for(Rint i = n - 1;~i;i --)
l[i] = pa.insert(str[i] - 'a');
pa.init();
for(Rint i = 0;i < n - 1;i ++)
ans = max(ans, l[i + 1] + pa.insert(str[i] - 'a'));
printf("%d", ans);
}