BZOJ2565: 最长双回文串【manacher】

2565: 最长双回文串

【题目描述】

传送门

【题解】

首先肯定要求出当前的回文,那么manacher就可以了。
如何找到双回文,这两个回文肯定能拼在一起,如果i回文能和多个回文拼一起,那么最长的肯定是回文中心最远的那个。
最后双回文长度就是两个回文长度加和-两倍的相交的长度。

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=100005;
int n,Ans,L[MAXN<<1],p[MAXN<<1];char ch[MAXN],s[MAXN<<1];
void manacher(){
    int R=0,pos=0;
    for(int i=1;i<=n;i++){
        if(i<R) p[i]=min(p[2*pos-i],R-i);else p[i]=1;
        while(i-p[i]>=1&&i+p[i]<=n&&s[i-p[i]]==s[i+p[i]]) p[i]++;
        if(i+p[i]>R) R=i+p[i],pos=i; 
    }
}
int main(){
    scanf("%s",ch+1);n=strlen(ch+1);
    for(int i=1;i<=n;i++) s[i<<1]=ch[i],s[(i<<1)-1]='%';
    s[(n<<1)+1]='%',n=(n<<1)+1;
    manacher();
    for(int i=1,j=1;i<=n;i++) while(j<=i+p[i]-1) L[j++]=i;
    for(int i=2;i<=n;i++){
        int j=L[i-p[i]],Del=p[i]+p[j]-(i-j)-1;
        Ans=max(Ans,i+p[i]-1-(j-p[j])-Del);
    }
    printf("%d\n",Ans/2);
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部