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

题目描述

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为abc，逆序为cba，不相同）。

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

输入格式：

一行由小写英文字母组成的字符串S。

输出格式：

一行一个整数，表示最长双回文子串的长度。

题解

考虑枚举两个回文子串的交界，那么就只要算出每个位置向左和向右能延伸的最大回文长度。

以向左为例，我们只需要找到，最靠左的包含他的回文串即可，这样长度是最大的。

#include<bits/stdc++.h>
using namespace std;
const int maxn=200005;
int n,ans;
char s[maxn],t[maxn];
int pl[maxn],l[maxn],r[maxn];

void manacher(){
    n=strlen(t);
    s[0]='+';
    for(int i=1;i<2*n;i+=2){
        s[i]='#';
        s[i+1]=t[i/2];
    }
    s[2*n+1]='#';
    s[2*n+2]='-';
    s[2*n+3]='';
    n=n*2+1;
    int mx=0,id=0;
    for(int i=1;i<=n;i++){
        if(mx>=i) pl[i]=min(mx-i+1,pl[2*id-i]);
        else pl[i]=1;
        while(s[i+pl[i]]==s[i-pl[i]]) pl[i]++;
        if(mx<pl[i]+i-1) mx=pl[i]+i-1,id=i;
    }
}

int main(){
    scanf("%s",t);
    manacher();
    for(int i=1,j=0;i<=n;j=max(j,i+pl[i]-1),i++)//找最靠左的包含k的回文串，l存长度 
     for(int k=j+1;k<=i+pl[i]-1;k++)
      l[k]=k-i;
    for(int i=n,j=n+1;i;j=min(j,i-pl[i]+1),i--)
     for(int k=j-1;k>=i-pl[i]+1;k--)
      r[k]=i-k;
    for(int i=3;i<=n-2;i+=2)//枚举#，不能枚举1,和n位置，因为这两个有一边没有字符 
     ans=max(ans,r[i]+l[i]);
    printf("%d",ans);
}