HDU 5371(2015多校7)-Hotaru's problem(Manacher算法求回文串)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了HDU 5371(2015多校7)-Hotaru's problem(Manacher算法求回文串)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1791字，纯文字阅读大概需要3分钟。
内容图文
题目地址：HDU 5371
题意：给你一个具有n个元素的整数序列，问你是否存在这样一个子序列，该子序列分为三部分，第一部分与第三部分相同，第一部分与第二部分对称，如果存在求最长的符合这种条件的序列。
思路：用Manacher算法来处理回文串的长度，记录下以每一个-1(Manacher算法的插入)为中心的最大回文串的长度。然后从最大的开始穷举，只要p[i]-1即能得出以数字为中心的最大回文串的长度，然后找到右边对应的’-1’，判断p[i]是不是大于所穷举的长度，如果当前的满足三段，那么就跳出，继续下一个以数字为中心的回文串。
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <map>
#pragma comment(linker, "/STACK:102400000,102400000")
using
namespace
std;
typedef __int64 LL;
constint inf=0x3f3f3f3f;
constdouble pi= acos(-1.0);
constdouble esp=1e-7;
constint Maxn=100005;
int str[Maxn];
int s[Maxn*2];
int p[Maxn*2];
int n;
void Manacher()
{
memset(p,0,sizeof(p));
s[0]=-2;
s[1]=-1;
for (int i=0;i<n;i++) {
s[i*2+2]=str[i];
s[i*2+3]=-1;
}
int MaxL=0,id=0;
for (int i=2; i<2*n+1; i++) {
if (p[id]+id>i)
p[i]=min(p[2*id-i],p[id]+id-i);
else
p[i]=1;
while (s[i-p[i]]==s[i+p[i]])
p[i]++;
if(id+p[id]<i+p[i])
id = i;
if (p[i]>MaxL)
MaxL=p[i];
}
}
int main()
{
int T,i;
int Max;
int ans;
int icase=1;
scanf("%d",&T);
while(T--) {
Max=0;
scanf("%d",&n);
for(i=0; i<n; i++)
scanf("%d",&str[i]);
Manacher();
for(i=3; i<2*n+1;i+=2){
ans=p[i]-1;
while(ans>Max&&p[i+ans]<ans)
ans--;
Max=max(Max,ans);
}
printf("Case #%d: %d\n",icase++,Max/2*3);
}
return0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
(Manacher算法求回文串)' ref='nofollow'>HDU 5371(2015多校7)-Hotaru's problem(Manacher算法求回文串)
原文：http://blog.csdn.net/u013486414/article/details/47446511
内容总结
以上是互联网集市为您收集整理的HDU 5371(2015多校7)-Hotaru's problem(Manacher算法求回文串)全部内容，希望文章能够帮你解决HDU 5371(2015多校7)-Hotaru's problem(Manacher算法求回文串)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。