hdu3294 manacher算法
2024-09-27 23:39:11
这道题哇 其实是裸的manacher 无论怎么变 是回文的就是回文 所以 特殊处理一下输出就好了 不过最后的左右端点l,r。l=(p-p[pos]+2)/2-1,r=(p+p[pos]-2)/2-1; 这个自己看一下就okay呐
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=;
int len,id,p[M],ans,pos,k;
char T[],s[M];
int main()
{
while(~scanf("%s %s",T,s)){
memset(p,,sizeof(p));
len=strlen(s); ans=; id=; pos=; k=T[]-'a';
for(int i=len;i>=;i--) s[i*+]=s[i],s[i*+]='#';
s[]='&'; len=len*+;
for(int i=;i<=len;i++){
if(id+p[id]>i) p[i]=min(p[id*-i],id+p[id]-i);
else p[i]=;
while(s[i-p[i]]==s[i+p[i]]) p[i]++;
if(p[i]>ans) ans=p[i],pos=i;
if(id+p[id]<i+p[i]) id=i;
}
int l=(pos-p[pos]+)/-,r=(pos+p[pos]-)/-;
if((r-l+)<){printf("No solution!\n"); continue;}
printf("%d %d\n",l,r);
for(int i=pos-p[pos]+;i<=pos+p[pos]-;i+=) printf("%c",(s[i]-'a'-k+)%+'a'); printf("\n");
}
return ;
}
最新文章
- 使用Angular2理由
- rabbitmq_hearbeat
- js类(继承)(二)
- 使用Sqlserver Management Studio 导入导出 Excel的方法
- [js]事件综合 整理
- iOS开发环境C语言基础 运算符和表达式
- .NET MVC4.0与CA对接
- Redis客户端之Spring整合Jedis
- C#“同步调用”、“异步调用”、“异步回调”
- 华为oj - 统计大写字母个数
- Linux开机自启动
- 初识JSON
- Python—day17时间模块、系统模块、递推遍历、序列化
- Excel列A、B、C、D----与列序号的转换
- Linux学习笔记11—VSFTP的搭建
- Online
- [WCF REST] 一个简单的REST服务实例
- RequestHelper
- Nodejs-- web服务器
- python进阶之py文件内置属性