String/manacher.hpp

• View this file on GitHub
• Last update: 2024-07-06 20:37:29+09:00
• Include: #include "String/manacher.hpp"

Verified with

• verify/manacher.test.cpp

Code

struct manacher {
    string s;
    int n, sz;
    vec<int> res;

    manacher(string S) : s(S) {
        n = s.size();
        string t = "";
        rep(i, 0, n) {
            t += s[i];
            if(i != n-1) t += "$";
        }
        sz = t.size();
        res = vec<int>(sz, 0);

        int c = 0;
        rep(i, 0, sz) {
            int l = 2 * c - i;
            if(i + res[l] < c + res[c]) res[i] = res[l];
            else {
                int j = c + res[c] - i;
                while(i - j >= 0 && i + j < sz && t[i-j] == t[i+j]) j++;
                res[i] = j;
                c = i;
            }
        }
    }

    int get(int p) {
        return (res[2 * p] + 1)/2;
    }

    int get(int l, int r) {
        int m = 2 * l + 1;
        return res[m]/2;
    }

};

#line 1 "String/manacher.hpp"
struct manacher {
    string s;
    int n, sz;
    vec<int> res;

    manacher(string S) : s(S) {
        n = s.size();
        string t = "";
        rep(i, 0, n) {
            t += s[i];
            if(i != n-1) t += "$";
        }
        sz = t.size();
        res = vec<int>(sz, 0);

        int c = 0;
        rep(i, 0, sz) {
            int l = 2 * c - i;
            if(i + res[l] < c + res[c]) res[i] = res[l];
            else {
                int j = c + res[c] - i;
                while(i - j >= 0 && i + j < sz && t[i-j] == t[i+j]) j++;
                res[i] = j;
                c = i;
            }
        }
    }

    int get(int p) {
        return (res[2 * p] + 1)/2;
    }

    int get(int l, int r) {
        int m = 2 * l + 1;
        return res[m]/2;
    }

};

Back to top page