题目地址：http://ac.jobdu.com/problem.php?pid=1528
- 题目描述：
-
回文串就是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
回文子串，顾名思义，即字符串中满足回文性质的子串。
给出一个只由小写英文字符a,b,c...x,y,z组成的字符串，请输出其中最长的回文子串的长度。
- 输入：
-
输入包含多个测试用例，每组测试用例输入一行由小写英文字符a,b,c...x,y,z组成的字符串，字符串的长度不大于200000。
- 输出：
-
对于每组测试用例，输出一个整数，表示该组测试用例的字符串中所包含的的最长回文子串的长度。
- 样例输入：
-
abab
bbbb
abba
- 样例输出：
-
3
4
4
自己比较野蛮的方法
#include <stdio.h>
#include <string.h> int LenOfMaxPalindrome(char str[], int len, int low, int high){
int sum = 0;
while (low >= 0 && high < len){
if (str[low] == str[high]){
sum += 2;
--low;
++high;
}
else
break;
}
return sum;
} int MaxPalindrome (char str[]){
int len = strlen (str);
int mid;
int len1;
int len2;
int max; if ((len >= 2) && (str[0] == str[1]))
max = 2;
else
max = 1;
for (mid=1; mid<len-1; ++mid){
len1 = len2 = 0;
len1 = LenOfMaxPalindrome(str, len, mid - 1, mid + 1) + 1;
if (str[mid] == str[mid + 1]){
len2 = LenOfMaxPalindrome(str, len, mid - 1, mid + 2) + 2;
}
if (len1 < len2)
len1 = len2;
if (max < len1)
max = len1;
} return max;
} int main(void){
char str[200001]; while (scanf ("%s", str) != EOF){
printf ("%d\n", MaxPalindrome (str));
} return 0;
}
O(n)的回文子串Manacher算法（详细算法讲解见参考资料）
算法代码实现如下：
#include <stdio.h>
void Manacher (char str[], int len, int Radix[]){
int mx = 0; //记录被影响到的最远的位置
int id = 0; //最长影响串的位置
Radix[0] = 0;
int i;
for (i=1; i<len; ++i){
Radix[i] = 1;
if (mx > i){
Radix[i] = Radix[2 * id - i];
if (mx - i < Radix[i])
Radix[i] = mx - i;
}
while (str[i - Radix[i]] == str[i + Radix[i]])
++Radix[i];
if (i + Radix[i] > mx){
mx = i + Radix[i];
id = i;
}
}
}
int Preproccess (char str[], char old_str[]){
int index;
int len;
char middle = '#';
str[0] = '$';
str[1] = middle;
index = 0;
len = 2;
while (old_str[index]){
str[len++] = old_str[index++];
str[len++] = middle;
}
str[len] = '?';
return len;
}
int main(void){
char old_str[200001];
char str[400004];
int Radix[400004];
int len;
int i;
int ans;
while (scanf ("%s", old_str) != EOF){
len = Preproccess (str, old_str);
Manacher (str, len, Radix);
ans = 0;
for (i=1; i<len; ++i){
if (ans < Radix[i])
ans = Radix[i];
}
printf ("%d\n", ans - 1);
}
return 0;
}
参考资料：http://tiankonguse.com/blog/?p=84
http://www.cnblogs.com/biyeymyhjob/archive/2012/10/04/2711527.html
http://www.akalin.cx/longest-palindrome-linear-time
http://leetcode.com/2011/11/longest-palindromic-substring-part-i.html
http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html
相思题目：https://oj.leetcode.com/problems/longest-palindromic-substring/