九度OJ 1528 最长回文子串 -- Manacher算法

回文串就是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串。
回文子串，顾名思义，即字符串中满足回文性质的子串。
给出一个只由小写英文字符a,b,c...x,y,z组成的字符串，请输出其中最长的回文子串的长度。

输入包含多个测试用例，每组测试用例输入一行由小写英文字符a,b,c...x,y,z组成的字符串，字符串的长度不大于200000。

对于每组测试用例，输出一个整数，表示该组测试用例的字符串中所包含的的最长回文子串的长度。

abab
bbbb
abba

3
4
4

腾讯2013年实习生招聘二面面试题

自己比较野蛮的方法

#include 
    
     
#include 
     
       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
      
       
 






       
O(n)的回文子串Manacher算法（详细算法讲解见参考资料）
       
算法代码实现如下：
       
 
       
#include 
        
         
 
void Manacher (char str[], int len, int Radix[]){
    int mx = 0;    //记录被影响到的最远的位置
    int id = 0;    //最长影响串的位置
    Radix[0] = 0;
    int i;
    for (i=1; i
         
           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
          
            参考资料：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