hdu5371Hotaru's problem manacher算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了hdu5371Hotaru's problem manacher算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1222字，纯文字阅读大概需要2分钟。
内容图文
//给一个序列。让求其最大子序列
//这个序列由三段组成。第一段和第二段对称,第一段和第三段一样
//manacher算法求得p[i]
//枚举第二段的起点和长度，得到结果
#include<cstdio>
#include<cstring>
#include<iostream>
using
namespace
std ;
constint maxn = 2e5 + 10 ;
int str[maxn] ;
int p[maxn] ;
void pk(int n)
{
int i;
int mx = 0;
int id=0;
for(i=0; i<n; i++)
{
if( mx > i )
p[i] = min( p[2*id-i], mx-i );
else
p[i] = 1;
for(; str[i+p[i]] == str[i-p[i]] && i - p[i] >= 0 && i + p[i] < n; p[i]++);
if( p[i] + i > mx )
{
mx = p[i] + i;
id = i;
}
}
}
int main()
{
int t ;
int cas = 0 ;
int n ;
scanf("%d" , &t) ;
while(t--)
{
scanf("%d" , &n) ;
for(int i = 0;i <= 2*n+1;i++)
p[i] = 0 ;
int len = 0 ;
str[len++] = -1 ;
for(int i = 1;i <= n;i++)
{
scanf("%d" , &str[len++]) ;
str[len++] = -1 ;
}
int ans = 1 ;
pk(len) ;
for(int i = 2;i < len-1 ;i += 2)
for(int j = ans;j <= p[i] ;j += 2)
if(p[i + j -1]>= j)
ans = j;
ans = ans/2*3 ;
printf("Case #%d: ",++cas) ;
cout<<ans<<endl;
}
return0 ;
}
hdu5371Hotaru's problem manacher算法
原文：http://www.cnblogs.com/liguangsunls/p/7142581.html
内容总结
以上是互联网集市为您收集整理的hdu5371Hotaru's problem manacher算法全部内容，希望文章能够帮你解决hdu5371Hotaru's problem manacher算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】