HDU3068 KMP求最长回文子串.pdf

九野的博客
ACM 今天你AC了吗? 欢迎acmer讨论~ 群号:126270450
HDU3068 KMP求最长回文子串
分类: KMP 2013-12-16 17:04 176人阅读评论(0) 收藏举报
 解析详见:http://blog./s/
 
 
 
#include<>
#include<>
#include<iostream>
using namespace std;
#define N 225000
//dp[i] 表示以i点为中心向右最大回文长度
//则答案就是max(dp[i]) -1
int dp[N];
char P[N], T[N];
//在每一个字符间插入# 这样得到的回文串长度一定是奇数(包含#)
int Have_P(){
int j, len = strlen(T);
j = 0;
P[j++] = '$';
P[j++] = '#';
for(int i = 0; i < len; i++)
P[j++] = T[i], P[j++] = '#';
P[j] = '\0';
return j;
}
void KMP(int Plen){
int mx = 0, id = 0;
dp[0] = 0;
for(int i = 1; i < Plen; i++)
{
dp[i] = mx>i? min(dp[2*id-i], mx-i) : 1;
while(P[i + dp[i]] == P[i - dp[i]])dp[i]++;
if(i + dp[i] > mx)
{
mx = dp[i] + i;
id = i;
}
}
}
int main(){
while(~scanf("%s", T)){
int len, ans = 0;
KMP(len = Have_P());
for(int i = 0; i < len; i++)
ans = max(ans, dp[i]-1);
printf("%d\n",ans);
}
return 0;
1
}
 
更多
上一篇:HDU 2087 KMP裸题
下一篇:HDU 1867 KMP 求最大尾部重叠
顶
0
踩
0
查看评论
* 以上用户言论只代表其个人观点,不代表CSDN网站的观点或立场

核心技术类目
全部主题 Java VPN Android iOS ERP IE10 Eclipse CRM JavaScript Ubuntu NFC WAP jQuery 数据库 BI HTML5
Spring Apache Hadoop .NET API HTML SDK IIS Fedora XML LBS Unity Splashtop ponents
Windows Mobile Rails QEMU KDE Cassandra CloudStack FTC coremail OPhone CouchBase 云计算 iOS6
Rackspace Web App Sprin