BZOJ2565 最长双回文串

Description

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

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

Input

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

Output

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

Sample Input

baacaabbacabb

Sample Output

HINT

从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。

对于100%的数据，2≤|S|≤10^5

板子，处理一下以每个点为左右端点两边的回文串长度，再跑一遍就好了

有一个处理，对于一个节点左边和右边的最长回文半径是可以进行递推的

l[i]=max(l[i+2]−2,l[i])" role="presentation">l[i]=max(l[i+2]−2,l[i])l[i]=max(l[i+2]−2,l[i])

r[i]=max(r[i−2]−2,r[i])" role="presentation">r[i]=max(r[i−2]−2,r[i])r[i]=max(r[i−2]−2,r[i])

#include<bits/stdc++.h>

using namespace std;

#define N 100010

int n=0,len,p[N<<1];

int l[N<<1]={0},r[N<<1]={0};

bool ll[N<<1],rr[N<<1];

char s[N<<1],t[N];

void Manacher(){

    int id=0,pos=0,x;

    for(int i=1;i<n;i++){

        if(pos>i)x=min(p[id*2-i],pos-i+1);

        else x=0;

        while(s[i-x]==s[i+x])x++;

        x--;

        if(i+x>pos)pos=i+x,id=i;

        p[i]=x;

    }

}

int main(){

    scanf("%s",t);

    n=0,len=strlen(t);

    s[0]='!';

    for(int i=0;i<len;i++){

        s[++n]='#';

        s[++n]=t[i];

    }

    s[++n]='#';

    s[++n]='?';

    Manacher();

    int ans=0;

    for(int i=1;i<n;i++){

        l[i+p[i]-1]=max(l[i+p[i]-1],p[i]);

        r[i-p[i]+1]=max(r[i-p[i]+1],p[i]);

    }

    for(int i=n;i>=2;i--)l[i]=max(l[i+2]-2,l[i]);

    for(int i=2;i<=n;i++)r[i]=max(r[i-2]-2,r[i]);

    for(int i=2;i<n;i+=2)ans=max(ans,l[i]+r[i+2]);

    printf("%d",ans);

    return 0;

}

巴特西

BZOJ2565 最长双回文串【Manacher】

BZOJ2565 最长双回文串

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

巴特西

BZOJ2565 最长双回文串 【Manacher】

BZOJ2565 最长双回文串

Description

Input

Output

Sample Input

Sample Output

HINT

最新文章

热门文章

BZOJ2565 最长双回文串【Manacher】