manacher.hpp

View this file on GitHub
Last update: 2024-09-22 15:35:16+09:00
Include: #include "manacher.hpp"

Verified with

test/lc_enumerate_palindromes.cpp

Code

vector<int> manacher(string s) {
    int n = s.size();
    vector<int> r(n, 1);
    int c = 0;
    for (int i = 0; i < n; ++i) {
        int j = c - (i - c);
        if (i + r[j] < c + r[c]) {
            r[i] = r[j];
        } else {
            int ri = c + r[c] - i;
            while (0 <= i - ri && i + ri < n && s[i - ri] == s[i + ri]) ri++;
            r[i] = ri;
            c = i;
        }
    }
    return r;
}

#line 1 "manacher.hpp"
vector<int> manacher(string s) {
    int n = s.size();
    vector<int> r(n, 1);
    int c = 0;
    for (int i = 0; i < n; ++i) {
        int j = c - (i - c);
        if (i + r[j] < c + r[c]) {
            r[i] = r[j];
        } else {
            int ri = c + r[c] - i;
            while (0 <= i - ri && i + ri < n && s[i - ri] == s[i + ri]) ri++;
            r[i] = ri;
            c = i;
        }
    }
    return r;
}