HDU - 3068 最长回文

题目大意: 给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度.

解题思路：Manacher算法

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

char S[110005], str[220010];
int len, p[220010];

void init() {
    len = strlen(S);
    str[0] = ‘$‘;
    str[1] = ‘#‘;
    for (int i = 0; i < len; i++) {
        str[2 * i + 2] = S[i]; 
        str[2 * i + 3] = ‘#‘;
    }
    len = 2 * len + 2;
    str[len] = 0;
}

int solve() {
    int MAX = 0, id = 0, ans = 1;
    for (int i = 1; i < len; i++) {
        if (MAX > i) 
            p[i] = min(p[2 * id - i], MAX - i);
        else
            p[i] = 1;

        while (str[i + p[i]] == str[i - p[i]])
            p[i]++;

        if (i + p[i] > MAX) {
            MAX = i + p[i];
            id = i;
        }

        ans = max(ans, p[i]);
    }

    return ans - 1;
}

int main() {
    while (scanf("%s", S) != EOF) {
        init();
        printf("%d\n", solve());
    }
    return 0;
}