bzoj 2565: 最长双回文串 manacher算法

2023-08-15 22:34:04

2565: 最长双回文串

Time Limit: 20 Sec Memory Limit: 256 MB

题目连接

http://www.lydsy.com/JudgeOnline/problem.php?id=2565

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

题意

题解：

马拉车算法先跑一法回文串长度，然后再dp一下，对于每个字符的位置，记录下这个点为左端点的回文串长度，这个点为右端点的回文串长度

对于如何存dp的值，我是暴力的，再加了个小小的剪枝

然后跑一法就好了

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+;

char s[maxn];

char str[maxn];

int p[maxn];

int dp1[maxn];

int dp2[maxn];

int l;

void manacher(char s[],int l)

{

   int i,j,k,ans=;

   for(i=;i<=l;++i)str[i<<]=s[i],str[(i<<)+]='#';

   str[]='#';str[l*+]='#';str[]='&';str[l*+]='$';

   l=l*+;j=;

   for(i=;i<=l;)

   {

       while(str[i-j-]==str[i+j+])++j;

       p[i]=j;if(j>ans)ans=j;

       for(k=;k<=j&&p[i]-k!=p[i-k];++k)p[i+k]=min(p[i-k],p[i]-k);

       i+=k;j=max(j-k,);

   }

}

int main()

{

    //test;

    scanf("%s",s+);

    l=strlen(s+);

    manacher(s,l);

    l=l*+;

    for(int i=;i<=l;i++)

    {

        for(int j=p[i];j>=;j--)

        {

            if(dp1[i+j]>=j)

                break;

            dp1[i+j]=j;

        }

        for(int j=p[i];j>=;j--)

        {

            if(dp2[i-j]>=j)

                break;

            dp2[i-j]=j;

        }

    }

    int ans=;

    for(int i=;i<=l-;i++)

    {

        if(dp1[i]&&dp2[i])ans=max(ans,dp1[i]+dp2[i]);

    }

    cout<<ans<<endl;

}

码农公寓