[字符串] 最长回文子串 manacher算法模板题 HDU3068

学习了一下这个算法,emmm不知道什么时候就会用到的感觉。本身功能是在O(n)时间内算出一个串的最长回文子串,其实这个过程也把每个点作为中心的最长回文串计算了一遍

这个算法的话主要是利用回文串的性质,回头整理好了再详细写。

#include
#include
#include
#include
#include
#include
#include
#include
#include
//#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=110005;
const int MOD=20071027;

char ori[maxn],p[maxn<<1];
int len[maxn<<1];

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    while(~scanf(" %s",ori))
    {
        //getchar();
        int n=strlen(ori);
        p[0]='$';
        for (int i=1;i<=n+n;i+=2)
        {
            p[i]='#';
            p[i+1]=ori[i/2];
        }
        p[2*n+1]='#';
        p[2*n+2]='&';
        int mx=0,po=0,ans=0;
        for (int i=1;i<=n+n;i++)
        {

            if(mx>i)
                len[i]=min(len[2*po-i],mx-i+1);
            else
                len[i]=1;
            while(p[i-len[i]]==p[i+len[i]])len[i]++;
            if(len[i]+i-1>mx)
            {
                mx=len[i]+i-1;
                po=i;
            }
            ans=max(ans,len[i]);
        }
        printf("%d\n",ans-1);
    }
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据