Manacher算法

#include <iostream>
#include <cstring>
using namespace std;

#define max_n 10000212
char s[max_n];
char s_new[max_n];
int p[max_n];


int init() {
    int len = strlen(s);
    s_new[0] = '$';
    s_new[1] = '#';
    int j = 2;
    for (int i = 0 ;i < len; i++) {
        s_new[j++] = s[i];
        s_new[j++] = '#';
    }
    s_new[j] = '\0';
    return j;
}

int Manacher() {
    int len = init();
    int id = 0;
    int mx = 0;
    int max_len = -1;
    for (int i = 1; i <= len; i++) {
        if (i < mx) {
            p[i] = min(p[2 * id - i] , mx - i);
        }else p[i] = 1;

        while (s_new[i - p[i]] == s_new[i + p[i]]) {
            p[i]++;
        }       
        if (i + p[i] > mx) {
            id = i;
            mx = i + p[i];
        }
        max_len = max(max_len, p[i] - 1);
    }
    return max_len;
}


int main() {

    cin >> s;
    cout << Manacher() << endl;
    return 0;
}