manacher 模板备份

#include <array>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

void manacher(const string &s, int m[]) {
    string a;
    const int len = s.length();
    int l = 0;
    a[l++] = '$';
    a[l++] = '#';
    for (int i = 0; i < len; i++) {
        a[l++] = s[i];
        a[l++] = '#';
    }
    a[l] = 0;
    int mx = 0, id = 0;
    for (int i = 0; i < l; i++) {
        m[i] = mx > i ? min((int)m[2 * id - i], mx - i) : 1;
        while (a[i + m[i]] == a[i - m[i]]) m[i]++;
        if (i + m[i] > mx) {
            mx = i + m[i];
            id = i;
        }
    }
}

int m[1000];

int main() {
    string s;
    cin >> s;
    manacher(s, m);
    for (int i = 0; i <= 2 * s.length(); i++) {
        printf("%3d", i);
    }
    putchar('\n');
    for (int i = 0; i <= 2 * s.length(); i++) {
        if (i != 0 && i % 2 == 0)
            printf("  %c", s[i / 2 - 1]);
        else
            printf("   ");
    }
    putchar('\n');
    for (int i = 0; i <= 2 * s.length(); i++) {
        printf("%3d", m[i] - 1);
    }
}

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.