Manacher's algorithm (src/string/manacher.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-03-15 03:09:02+09:00
• Include: #include "src/string/manacher.hpp"

列に含まれる回文を高速に扱うためのアルゴリズム。

文字位置と文字間をあわせた $2n+1$ 個の中心それぞれについて， 回文の情報を $O(n)$ で求める。

---

型

• T：== で比較可能な型

---

関数

template <class T>
std::vector<int> manacher(const std::vector<T>& s)

列 s に対する Manacher の結果を返す。

返り値 ret の長さは

\[2|s|+1\]

である。

添字 i は次を表す。

• i = 2k+1 ：s[k] を中心とする
• i = 2k ：s[k-1] と s[k] の間を中心とする

ret[i] はその中心における回文の大きさを表す。

区間 $[l, r)$ が回文であることと

\[\mathrm{ret}[l+r] \ge r-l+1\]

は同値である。

制約

\[0 \le |s|\]

計算量

\[O(|s|)\]

---

std::vector<int> manacher(const std::string& s)

文字列 s に対する Manacher の結果を返す。

返り値・意味・計算量は vector<T> 版と同様。

制約

\[0 \le |s|\]

計算量

\[O(|s|)\]

---

備考

奇数長回文と偶数長回文を統一的に扱える。

---

Verified with

• src/verify/yosupo-enumerate-palindromes.test.cpp

Code

#pragma once

#include <cassert>
#include <string>
#include <vector>

namespace akTARDIGRADE13 {

template <class T>
std::vector<int> manacher(const std::vector<T>& s) {
    int n = s.size();
    std::vector<int> ret(n << 1 | 1);
    int sz = ret.size();
    int i = 1, j = 1;
    while (i < sz) {
        while (j < i && i + j < (n << 1) && s[((i - j) >> 1) - 1] == s[(i + j) >> 1]) {
            j += 2;
        }
        ret[i] = j;
        if (j == 0) {
            i++;
            j = 1;
            continue;
        }
        int k = 1;
        while (k <= i && k + ret[i - k] < j) {
            ret[i + k] = ret[i - k];
            k++;
        }
        i += k;
        j -= k;
    }
    return ret;
}

std::vector<int> manacher(const std::string& s) {
    int n = s.size();
    std::vector<int> ret(n << 1 | 1);
    int sz = ret.size();
    int i = 1, j = 1;
    while (i < sz) {
        while (j < i && i + j < (n << 1) && s[((i - j) >> 1) - 1] == s[(i + j) >> 1]) {
            j += 2;
        }
        ret[i] = j;
        if (j == 0) {
            i++;
            j = 1;
            continue;
        }
        int k = 1;
        while (k <= i && k + ret[i - k] < j) {
            ret[i + k] = ret[i - k];
            k++;
        }
        i += k;
        j -= k;
    }
    return ret;
}

} // namespace akTARDIGRADE13

#line 2 "src/string/manacher.hpp"

#include <cassert>
#include <string>
#include <vector>

namespace akTARDIGRADE13 {

template <class T>
std::vector<int> manacher(const std::vector<T>& s) {
    int n = s.size();
    std::vector<int> ret(n << 1 | 1);
    int sz = ret.size();
    int i = 1, j = 1;
    while (i < sz) {
        while (j < i && i + j < (n << 1) && s[((i - j) >> 1) - 1] == s[(i + j) >> 1]) {
            j += 2;
        }
        ret[i] = j;
        if (j == 0) {
            i++;
            j = 1;
            continue;
        }
        int k = 1;
        while (k <= i && k + ret[i - k] < j) {
            ret[i + k] = ret[i - k];
            k++;
        }
        i += k;
        j -= k;
    }
    return ret;
}

std::vector<int> manacher(const std::string& s) {
    int n = s.size();
    std::vector<int> ret(n << 1 | 1);
    int sz = ret.size();
    int i = 1, j = 1;
    while (i < sz) {
        while (j < i && i + j < (n << 1) && s[((i - j) >> 1) - 1] == s[(i + j) >> 1]) {
            j += 2;
        }
        ret[i] = j;
        if (j == 0) {
            i++;
            j = 1;
            continue;
        }
        int k = 1;
        while (k <= i && k + ret[i - k] < j) {
            ret[i + k] = ret[i - k];
            k++;
        }
        i += k;
        j -= k;
    }
    return ret;
}

} // namespace akTARDIGRADE13

Back to top page