?
最长回文
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9188 Accepted Submission(s): 3159
?
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
aaaa
abab
Sample Output
4
3
Source 2009 Multi-University Training Contest 16 - Host by NIT
题目链接：www.2cto.com
题目分析：manacher算法是用来求解最长回文子串最简便的算法，下面最这个算法进行简要介绍：
定义数组p[i]表示以i为中心的(包含i这个字符)回文串半径长，将字符串s从前往后扫来计算p[i]，最后最大的p[i]就是最长回文串长度，下面阐述如何求解p数组：
由于s是从前往后扫的，所以需要计算p[i]时一定已经计算好了p[1]....p[i - 1]，假设现在扫描到了i + k这个位置，现在需要计算p[i + k]，定义maxp是i + k位置前所有回文串中能延伸到的最右端的位置，maxp = p[i] + i
分两种情况:
1）i + k这个位置不在前面的任何回文串中，即i + k > maxp，则初始化p[i + k] = 1（即本身是回文串）然后将p[i + k]向左右延伸，
即while(s[i + k + p[i + k]] == s[i + k - p[i + k]]) p[i + k] ++
2）i + k这个位置被前面以位置i为中心的回文串包含，即maxp > i + k，这样p[i + k]就不从1开始，由回文串的性质可知i + k这个位置关于i与 i - k对称，所以p[i + k]分为3种情况:
?
1. i - k回文串范围有一部分在p[i]之外，此时p[i + k] = p[i] - k，此时p[i + k]不可能更长，我们可以反证，假设还有一段d在之后，即
p[i + k] = p[i] - k + d，则根据回文性质可得此时得p[i] = p[i] + d，与p[i]矛盾，故不会更长。
?
2. i - k回文串范围全部在p[i]以内，此时p[i + k] = p[i - k]，这个很显然
?
3. i - k回文串范围刚好等于p[i]，此时p[i + k] = p[i - k]，且可能继续向左右延伸，
即while(s[i + k + p[i + k]] == s[i + k - p[i + k]]) p[i + k] ++
?
综合上述所有情况，我们可以得到
p[i + k] = min(p[i - k], p[i] - k)
while(s[i + k + p[i + k]] == s[i + k - p[i + k]])
p[i + k] ++
最后遇到长度为偶数的字符串我们要将其长度变成奇数，穿插未出现的字符即可，防止数组越界，s[0]我们也要设置成一个与''不同的字符
?
#include
#include
#include
using namespace std; int const MAX = 110005; char s[MAX << 1]; int p[MAX << 1]; int Manacher() { int len = strlen(s), maxp = 0, ans = 0; for(int i = len; i >= 0; i--) { s[i * 2 + 2] = s[i]; s[i * 2 + 1] = '#'; } s[0] = '*'; for(int i = 2; i < 2 * len + 1; i++) { if(p[maxp] + maxp > i) p[i] = min(p[2 * maxp - i], p[maxp] + maxp - i); else p[i] = 1; while(s[i - p[i]] == s[i + p[i]]) p[i]++; if(p[maxp] + maxp < i + p[i]) maxp = i; if(ans < p[i]) ans = p[i]; } return ans - 1; } int main() { while(scanf(%s, s) != EOF) printf(%d , Manacher()); }