首页 > 代码库 > HDU3068 最长回文
HDU3068 最长回文
本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。
本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!
Problem Description
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等
回文就是正反读都是一样的字符串,如aba, abba等
Input
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000
Output
每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
Sample Input
aaaa
abab
Sample Output
4
3
正解:manacher
解题报告:
manacher模板题。
题解左转:POJ3974我的博客:http://www.cnblogs.com/ljh2000-jump/p/6264712.html
//It is made by ljh2000 #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> using namespace std; typedef long long LL; const int MAXN = 250011; int n,p[MAXN],len,ans,maxR,id; char ch[MAXN],s[MAXN]; inline int getint(){ int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w; } inline void work(){ while(scanf("%s",ch)!=EOF) { len=strlen(ch); n=1; s[0]=‘%‘; s[1]=‘#‘; for(int i=0;i<len;i++) { s[++n]=ch[i]; s[++n]=‘#‘; } memset(p,0,sizeof(p)); ans=0; maxR=0; id=0; for(int i=1;i<=n;i++) { if(i<maxR) p[i]=min(p[2*id-i],maxR-i); else p[i]=1; for(;i+p[i]<=n && s[i-p[i]]==s[i+p[i]];p[i]++) ; if(i+p[i]>maxR) { maxR=i+p[i]; id=i; } } for(int i=1;i<=n;i++) ans=max(ans,p[i]); ans--; printf("%d\n",ans); } } int main() { work(); return 0; }
HDU3068 最长回文
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。