【HDU 3068】 最长回文

【题目链接】

http://acm.hdu.edu.cn/showproblem.php?pid=3068

【算法】

Manacher算法求最长回文子串

【代码】

#include<bits/stdc++.h>
using namespace std;
#define MAXN 110010 char s[MAXN]; inline void Manacher()
{
int i,len,ans = ,pos = ,mx = ;
static char tmp[MAXN<<];
static int p[MAXN<<];
len = strlen(s+);
for (i = ; i <= len; i++)
{
tmp[*i-] = '#';
tmp[*i] = s[i];
}
tmp[len = * len + ] = '#';
for (i = ; i <= len; i++)
{
if (mx > i) p[i] = min(p[*pos-i],mx-i);
else p[i] = ;
while (i - p[i] >= && i + p[i] <= len && tmp[i-p[i]] == tmp[i+p[i]]) p[i]++;
if (i + p[i] - > mx)
{
mx = i + p[i] - ;
pos = i;
}
}
for (i = ; i <= len; i++) ans = max(ans,p[i]-);
printf("%d\n",ans);
} int main()
{ while (scanf("%s",s+) != EOF) Manacher(); return ; }
上一篇:【HDU 5145】 NPY and girls(组合+莫队)


下一篇:【hdu 1043】Eight