最长回文

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 24272 Accepted Submission(s): 8912

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

　　传说中的manacher算法。。。。
　　

代码：

/* *Submit Time Judge Status Pro.ID Exe.Time Exe.Memory Code Len. Language *2017-10-07 Accepted 3068 390MS 2940K 1072 B G++ */
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

string S, W;
vector<int> p;

void init()//预处理数据
{
    int len = S.length();
    string &str = W;
    str.resize(2 * len + 2);
    str[0] = '$';//防止算法越界
    int idx = 1;
    for (int i = 0; i < len; i++) {
        str[idx++] = '#';
        str[idx++] = S[i];
    }
    str[idx++] = '#';
}

int manacher()
{
    init();
    int maxId = 0, center = 1, len = W.length();
    p.resize(len + 1);
    for (int i = 1; i < len; i++) {
        if (maxId > i) p[i] = min(maxId - i, p[2 * center - i]);
        else p[i] = 1;
        while (W[i - p[i]] == W[i + p[i]]) p[i]++;
        if (p[i] + i > maxId) {
            maxId = p[i] + i;
            center = i;
        }
    }
    int maxLen = 0;
    for (int i = 1; i < len; i++) {
        maxLen = max(p[i] - 1, maxLen);
    }
    return maxLen;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);//不关同步会超时。。。。。
    while (cin >> S) {
        cout << manacher() << endl;     
    }
    return 0;
}









//