http://hihocoder.com/contest/hiho1/problem/1

最长回文串，这里主要是Manacher算法
给定一个字符串，求出最长的回文串，一般会想到的是遍历中点，向两边扩展，但是这种方法对于极限情况每个点都被遍历了n次，是一个复杂度很高的算法，而Manacher算法为了解决这个问题，首先是把字符串扩展成一个新串，在每一字符的两边加入一个特殊字符，然后又引入了一个len数组，这个len数组代表的是以i为中心的回文串的半径+1
例如:Str:aabaac
newStr: # a # a # b # a # a # c

这个ｌｅｎ数组是有递推来的，又已经得到的最大的右边界Ｐ，对应的左边界p`和右边界所对应的中点ｋ
比如一个newStr中推到第ｉ位那么此时又两种可能
１.ｉ＜＝Ｐ

如图，i对应的点j的len值如果小于j-p,那么len[i] = len[j]
而如果j的len值大于j-p,那么就以i位中心，从p+1开始重新扩展，更新右边界，
而如果i>p
那么，就直接以i为中心，开始扩展

代码：

这里在字符串前面又加了一个$防止溢出

string LongestPalindrome(string s) {
    string newStr = "$#";
    for (int i = 0; i < s.size(); i ++) {
        newStr += s[i];
        newStr += '#';
    }
    vector<int> Len(newStr.size(), 0);
    int pos = 0, mx = 0;
    int sta = 0, maxLen = 0;
    for (int i = 1; i < newStr.size(); i ++) {
        Len[i] = i < mx ? min(Len[2*pos - i], mx - i) : 1;
        while(i + Len[i] < newStr.size() && i - Len[i] > 0 && newStr[i + Len[i]] == newStr[i - Len[i]])
            Len[i] ++;
        if(i + Len[i] > mx) {
            pos = i;
            mx = i + Len[i];
        }
        if(Len[i] - 1 > maxLen) {
            sta = (i - Len[i])/2;
            maxLen = Len[i] - 1;
        }
    }
    return s.substr(sta, maxLen);

hihoCoder AC代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 5;

string LongestPalindrome(string s) {
    string newStr = "$#";
    for (int i = 0; i < s.size(); i ++) {
        newStr += s[i];
        newStr += '#';
    }
    vector<int> Len(newStr.size(), 0);
    int pos = 0, mx = 0;
    int sta = 0, maxLen = 0;
    for (int i = 1; i < newStr.size(); i ++) {
        Len[i] = i < mx ? min(Len[2*pos - i], mx - i) : 1;
        while(i + Len[i] < newStr.size() && i - Len[i] > 0 && newStr[i + Len[i]] == newStr[i - Len[i]])
            Len[i] ++;
        if(i + Len[i] > mx) {
            pos = i;
            mx = i + Len[i];
        }
        if(Len[i] - 1 > maxLen) {
            sta = (i - Len[i])/2;
            maxLen = Len[i] - 1;
        }
    }
    return s.substr(sta, maxLen);
}

int main(int argc, char const *argv[]) {
    int T;
    cin >> T;
    while(T --) {
        string ss;
        cin >> ss;
        cout << LongestPalindrome(ss).size() << endl;
    }
    return 0;
}