Manacher 算法

LeetCode 5 Longest Palindromic Substring

class Solution {
public:
    string longestPalindrome(string s)
    {
        int len = (int)s.length();
        int n = len * 2 + 2;
        vector<int> mp(n, 0);
        string ma("$#");
        for (int i = 0; i < len; ++i) {
            ma.push_back(s[i]);
            ma.push_back('#');
        }
        int mx = 0, id = 0, p = 0;
        for (int i = 0; i < n; ++i) {
            mp[i] = mx > i ? min(mx - i, mp[id * 2 - i]) : 1;
            if (i == 0) continue;
            while (ma[i + mp[i]] == ma[i - mp[i]]) {
                ++mp[i];
            }
            if (mx < mp[i] + i) {
                mx = mp[i] + i;
                id = i;
            }
            if (mp[i] > mp[p]) {
                p = i;
            }
        }
        len = mp[p] - 1;
        p = (p - len) / 2;
        return s.substr(p, len);
    }
};

洛谷 P3805 【模板】manacher算法

#include <bits/stdc++.h>

using namespace std;
const int maxn = 11e6 + 10;
int mp[maxn << 1];
char s[maxn], ma[maxn << 1];

void manacher(int len)
{
    memset(mp, 0, sizeof mp);
    int l = 0;
    ma[l++] = '$';
    ma[l++] = '#';
    for (int i = 0; i < len; ++i) {
        ma[l++] = s[i];
        ma[l++] = '#';
    }
    ma[l] = '\0';
    int mx = 0, id = 0;
    for (int i = 0; i < l; ++i) {
        mp[i] = mx > i ? min(mx - i, mp[id * 2 - i]) : 1;
        while (ma[i + mp[i]] == ma[i - mp[i]]) ++mp[i];
        if (mx < mp[i] + i) {
            mx = mp[i] + i;
            id = i;
        }
    }
}

int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("input.txt", "r", stdin);
#endif
    scanf("%s", s);
    int len = (int)strlen(s);
    manacher(len);
    int res = 0;
    for (int i = 0; i < len * 2 + 2; ++i) {
        res = max(res, mp[i] - 1);
    }
    printf("%d\n", res);
    return 0;
}