Halc's Library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by halc-git Hosted on GitHub Pages — Theme by mattgraham

String/Manacher.hpp

• View this file on GitHub
• Last update: 2024-05-09 17:59:47+09:00
• Include: #include "String/Manacher.hpp"
• Link: https://snuke.hatenablog.com/entry/2014/12/02/235837

Verified with

• Verify/verify-yosupo-string/enumerate_palindromes.test.cpp

Code

#pragma once
#include <cstdint>
#include <vector>
// https://snuke.hatenablog.com/entry/2014/12/02/235837
template <typename S>
std::vector<int32_t> manacher(S s, bool is_even = true) {
    int32_t i = 0, j = 0, k, sz = (s.size() << is_even) - is_even;
    std::vector<int32_t> ret(sz);
    while (i < sz) {
        if (is_even) {
            while (i - j >= -1 && i + j <= sz &&
                   (((i - j) & 1) || s[(i - j) >> 1] == s[(i + j) >> 1]))
                j++;
        } else {
            while (i - j >= 0 && i + j < sz && s[i - j] == s[i + j]) j++;
        }
        ret[i] = j;
        k = 1;
        while (i - k >= 0 && k + ret[i - k] < j) {
            ret[i + k] = ret[i - k];
            k++;
        }
        i += k;
        j -= k;
    }
    for (int32_t i = 0; i < sz; i++) {
        if (is_even) {
            ret[i]--;
        } else {
            ret[i] = (ret[i] << 1) - 1;
        }
    }
    return ret;
}

#line 2 "String/Manacher.hpp"
#include <cstdint>
#include <vector>
// https://snuke.hatenablog.com/entry/2014/12/02/235837
template <typename S>
std::vector<int32_t> manacher(S s, bool is_even = true) {
    int32_t i = 0, j = 0, k, sz = (s.size() << is_even) - is_even;
    std::vector<int32_t> ret(sz);
    while (i < sz) {
        if (is_even) {
            while (i - j >= -1 && i + j <= sz &&
                   (((i - j) & 1) || s[(i - j) >> 1] == s[(i + j) >> 1]))
                j++;
        } else {
            while (i - j >= 0 && i + j < sz && s[i - j] == s[i + j]) j++;
        }
        ret[i] = j;
        k = 1;
        while (i - k >= 0 && k + ret[i - k] < j) {
            ret[i + k] = ret[i - k];
            k++;
        }
        i += k;
        j -= k;
    }
    for (int32_t i = 0; i < sz; i++) {
        if (is_even) {
            ret[i]--;
        } else {
            ret[i] = (ret[i] << 1) - 1;
        }
    }
    return ret;
}

Back to top page