首页 > 其他 > 详细

POJ3974Palindrome(Manacher)

时间:2019-12-08 14:51:48      阅读:80      评论:0      收藏:0      [点我收藏+]

传送门

题目大意:求最长回文串

题解:Manacher

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int maxn=1e6+5;
char s[maxn*2],str[maxn*2];
int Len[maxn*2],len;

void getstr()
{
    int k=0;
    str[k++]=$;
    for(int i=0;i<len;i++)
        str[k++]=#,
        str[k++]=s[i];
    str[k++]=#;
    len=k;
}

void Manacher()
{
    getstr();
    int mx=0,id;
    for(int i=1;i<len;i++)
    {
        if(mx>i) Len[i]=min(Len[2*id-i],mx-i);
        else Len[i]=1;
        while(str[i+Len[i]]==str[i-Len[i]]) 
            Len[i]++;
        if(Len[i]+i>mx)
            mx=Len[i]+i,id=i;
    }
}

int main()
{
    int n,js=0;
    for(;;)
    {
        scanf("%s",&s);
       // if(s=="END") break;
        if(s[0]==E&&s[1]==N&&s[2]==D) break;
        len=strlen(s);
        Manacher();
        int ans=1;
        for(int i=1;i<len;i++) ans=max(ans,Len[i]);
        printf("Case %d: %d\n",++js,ans-1);
    }
    return 0;
}

 

POJ3974Palindrome(Manacher)

原文:https://www.cnblogs.com/zzyh/p/12005436.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!