hdu 3068 最长回文子串 马拉车模板

前几天用后缀数组写过一次这题,毫无疑问很感人的TLE了-_-||

今天偶然发现了马拉车模板,O(N)时间就搞定

reference:http://acm.uestc.edu.cn/bbs/read.php?tid=3258

 #include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define N 110010
char s[N*],str[N*];
int n,p[N*]; void fun()
{
int len=(int)strlen(s);
str[]='$';str[]='#';
n=;
for(int i=;i<len;i++)
{
str[n++]=s[i];
str[n++]='#';
}
str[n]='\0';
} void Manacher()
{
int i,id,mx=;
for(i=;i<n;i++)
{
if(mx > i)
p[i]=min(p[*id-i],p[id]+id-i);
else
p[i]=;
for(;str[i+p[i]] == str[i-p[i]];p[i]++)
;
if(p[i]+i > mx)
{
mx=p[i]+i;
id=i;
}
}
} void work()
{
int ans=-;
for(int i=;i<n;i++)
ans=max(ans,p[i]);
printf("%d\n",ans-);
} int main()
{
while(scanf("%s",s)!=EOF)
{
fun();
Manacher();
work();
}
return ;
}
上一篇:通常每个套接字地址(协议/网络地址/端口)只允许使用一次。 数据库连接不释放测试 连接池 释放连接 关闭连接 有关 redis-py 连接池会导致服务器产生大量 CLOSE_WAIT 的再讨论以及一个解决方案


下一篇:Thinkphp--------为什么Thinkphp会默认进入Index控制器的index方法