解题思路：通过manachar算法求最长回文子串，如果用遍历的话绝对超时。
#include <stdio.h>
#include <string.h> const int N = 220005; int rad[N];
char string[N], tmpstr[N]; int max(int a, int b) {
return a > b ? a : b;
}
int min(int a, int b) {
return a < b ? a : b;
} int manachar() {
int ans = 0, mix = 0, id = 0, len = strlen(string);
for (int i = 1; i <= len; i++) {
if (mix > i)
rad[i] = min(rad[2 * id - i], mix - i);
else
rad[i] = 1; for ( ; string[i - rad[i]] == string[i + rad[i]]; rad[i]++) {
if (mix < i + rad[i]) {
mix = i + rad[i];
id = i;
}
} ans = max(ans, rad[i]);
}
return ans - 1;
} int main() {
while (gets(tmpstr)) {
int len = strlen(tmpstr), cnt = 0;
string[cnt++] = '$';
for (int i = 0; i <= len; i++) {
string[cnt++] = '#';
string[cnt++] = tmpstr[i];
}
getchar();
printf("%d\n", manachar());
}
return 0;}