题目链接......
最长回文
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1301 Accepted Submission(s): 313
Problem Description
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等
Input
输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000
Output
每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
Sample Input
Sample Output
Source
Recommend
lcy
代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;
#define max_size 110010
int next1[max_size];
int next2[max_size];
int next[max_size];
int ans;
char a[max_size];
char b[max_size];
void getNext1(int n)
{
int i, j, k;
next[0] = n;
j = 0;
while (j + 1 < n && b[j] == b[j+1])j++;
next[1] = j;
k = 1;
for (i = 2; i < n; i++)
{
if (next[i-k] + i < next[k] + k)
next[i] = next[i-k];
else
{
j = next[k] + k - i;
if (j < 0)j = 0;
while (i+j < n && b[j] == b[i+j])j++;
next[i] = j;
k = i;
}
}
}
void getNext2(char *s, int *nexts, int n, int m)
{
getNext1(m);
int i, j, k;
j = 0;
k = 0;
while (s[j] == b[j])j++;
nexts[0] = j;
for (i = 1; i < n; i++)
{
if (next[i-k] + i < nexts[k] + k)
nexts[i] = next[i-k];
else
{
j = nexts[k] + k - i;
if (j < 0) j = 0;
while (i + j < n && s[i+j] == b[j])j++;
nexts[i] = j;
k = i;
}
}
}
void res(char *s, int n)
{
char st;
int len = (n>>1);
for (int i = 0; i < len; i++)
{
st = s[i];
s[i] = s[n-i-1];
s[n-i-1] = st;
}
}
void find(char *s, int n)
{
if (ans >= n || n < 2)return;
int i, k, x;
int mid;
mid = (n>>1);
for (i = mid; i < n; i++)b[i-mid] = s[i];
b[i-mid] = 0;
res(s, n);
getNext2(s, next1, n, i-mid);
res(s, n);
for (i = 0; i < mid; i++)
b[i] = s[mid-i-1];
b[i] = 0;
getNext2(s, next2, n, mid);
next1[n] = next2[n] = 0;
for (i = 0; i < mid; i++)
{
if (next2[i] >= mid - i)
{
x = mid - i + 2 * next1[n-i];
if (ans < x)ans = x;
}
}
for (i = mid; i < n; i++)
{
if (next1[n-i] >= i - mid)
{
x = i - mid + 2*next2[i];
if (ans < x) ans = x;
}
}
find(s, mid);
find(s+mid, n-mid);
}
int main()
{
int n;
while (scanf("%s", a) != EOF)
{
n = strlen(a);
ans = 1;
find(a, n);
printf("%d\n", ans);
}
return 0;
}