最长回文
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7976 Accepted Submission(s): 2735Problem Description给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等Input输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000Output每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.Sample Inputaaaaabab
Sample Output4
3
关于Manacher算法的介绍，网上可以找到很多资料。O(N)
Accepted Code:
/*************************************************************************
> File Name: hdu_3068.cpp
> Author: Stomach_ache
> Mail: sudaweitong@gmail.com
> Created Time: 2014年08月04日 星期一 18时44分05秒
> Propose: hdu3068, poj3974
************************************************************************/
// Manacher O(n)
#include <cmath>
#include <string>
#include <cstdio>
#include <fstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int maxn = ;
char s[maxn], str[maxn<<];
int p[maxn<<], n; void Manacher() {
n = strlen(s);
str[] = '$';
str[] = '#';
for (int i = ; i < n; i++) {
str[i*+] = s[i];
str[i*+] = '#';
}
n = n * + ;
str[n] = ; int mx = ;
int id;
for (int i = ; i < n; i++) {
if (mx > i) p[i] = min(p[*id-i], mx - 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 solve() {
Manacher();
int ans = ;
for (int i = ; i < n; i++) ans = max(ans, p[i]);
printf("%d\n", ans - );
} int main(void) {
while (~scanf("%s", s)) {
solve();
} return ;
}