题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=3068

题解

Manacher算法,求字符串中最长回文子串的线性算法 。

代码

/*
 * Author: Haipz
 * School: HDU
 * File Name: 3068.cpp
 */
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cfloat>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

const int L = 2e5;
char s[L + 5], t[L*2 + 5];
int p[L*2 + 5];

int Manacher(char *s) {
    char st = '$', ct = '#';
    int n = (strlen(s) + 1)*2, mx = 0, id = 0, ans = 1;
    t[0] = st, t[1] = ct, t[n] = '\0';
    for (int i = 0; s[i]; ++i) t[(i + 1)*2] = s[i], t[(i + 1)*2 + 1] = ct;
    for (int i = 1; i < n; ++i) {
        if (mx > i) p[i] = min(p[id*2 - i], mx - i);
        else p[i] = 1;
        while (t[i - p[i]] == t[i + p[i]]) ++p[i];
        if (i + p[i] > mx) mx = i + p[i], id = i;
        ans = max(ans, p[i] - 1);
    }
    return ans;
}

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

转载保留版权:http://haipz.com/blog/i/1750 - 海胖博客