HDU 3068 最长回文(Manacher)

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

题目链接

求最长回文子串，Manacher算法模板题。

推荐一篇Manacher算法博客，很详细。

马拉车（manacher） 算法

AC代码:

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;

char ConvertStr[maxn << 1];
int Len[maxn << 1];

int Manacher(char Str[]) {
    int L = 0, StrLen = int(strlen(Str));
    ConvertStr[L++] = '$'; ConvertStr[L++] = '#';
    for (int i = 0; i < StrLen; ++i) {
        ConvertStr[L++] = Str[i];
        ConvertStr[L++] = '#';
    }
    int MX = 0, ID = 0, Ans = 0;
    for (int i = 0; i < L; ++i) {
        Len[i] = MX > i ? min(Len[2 * ID - i], MX - i) : 1;
        while (ConvertStr[i + Len[i]] == ConvertStr[i - Len[i]]) {
            Len[i]++;
        }
        if (i + Len[i] > MX) {
            MX = i + Len[i];
            ID = i;
        }
        Ans = max(Ans, Len[i] - 1);
    }
    return Ans;
}

char Str[maxn];

int main(int argc, char *argv[]) {
    while (~scanf("%s", Str)) {
        printf("%d\n", Manacher(Str));
    }
    return 0;
}