競プロノート

Appearance

Manacher（回文） ​

文字列の各位置を中心とする最長回文の半径を O(N) で求めるアルゴリズム。

奇数長・偶数長の回文をそれぞれ管理する。

イメージ ​

奇数長回文 ​

S = "abacaba"

i0123456
S[i]abacaba
odd[i]1214121

odd[i] は中心の文字自身を含む半径。

例えば odd[3] = 4 は、中心 c の回文 abacaba（長さ7）を意味する。

最長回文の長さは 2 * odd[i] - 1。

偶数長回文 ​

S = "abba"

i0123
S[i]abba
even[i]0020

even[i] は S[i-1] と S[i] の間を中心とする半径。

例えば even[2] = 2 は、2つの b の間を中心とする回文 abba（長さ4）を意味する。

最長回文の長さは 2 * even[i]。

特徴 ​

項目内容
用途回文判定・最長回文・回文の数え上げ
構築O(N)
区間の回文判定O(1)
最長回文の長さ・区間取得O(1)
回文部分文字列の総数O(N)
空間計算量O(N)

実装 ​

cpp

#pragma once
#include <algorithm>
#include <cassert>
#include <string>
#include <utility>
#include <vector>

struct Manacher {
    std::string s;
    int n = 0;
    std::vector<int> odd, even;
    int longest_left = 0, longest_right = 0;

    Manacher() = default;
    explicit Manacher(const std::string& s) { build(s); }

    void build(const std::string& str) {
        s = str;
        n = (int)s.size();
        odd.assign(n, 0);
        even.assign(n, 0);
        build_odd();
        build_even();
        find_longest();
    }

    void build_odd() {
        int l = 0, r = -1;
        for (int i = 0; i < n; i++) {
            int k = i > r ? 1 : std::min(odd[l + r - i], r - i + 1);
            while (i - k >= 0 && i + k < n && s[i - k] == s[i + k]) k++;
            odd[i] = k;
            if (i + k - 1 > r) {
                l = i - k + 1;
                r = i + k - 1;
            }
        }
    }

    void build_even() {
        int l = 0, r = -1;
        for (int i = 0; i < n; i++) {
            int k = i > r ? 0 : std::min(even[l + r - i + 1], r - i + 1);
            while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k]) k++;
            even[i] = k;
            if (i + k - 1 > r) {
                l = i - k;
                r = i + k - 1;
            }
        }
    }

    void update_longest(int l, int r) {
        if (r - l > longest_right - longest_left ||
            (r - l == longest_right - longest_left && l < longest_left)) {
            longest_left = l;
            longest_right = r;
        }
    }

    void find_longest() {
        longest_left = longest_right = 0;
        for (int i = 0; i < n; i++) {
            update_longest(i - odd[i] + 1, i + odd[i]);
            update_longest(i - even[i], i + even[i]);
        }
    }

    // s[l..r) が回文か O(1) で判定
    bool is_palindrome(int l, int r) const {
        if (l < 0 || r > n || l > r) return false;
        int len = r - l;
        if (len == 0) return true;
        if (len & 1) return odd[(l + r - 1) / 2] >= len / 2 + 1;
        return even[(l + r) / 2] >= len / 2;
    }

    int odd_length(int i) const { assert(0 <= i && i < n); return 2 * odd[i] - 1; }
    int even_length(int i) const { assert(0 <= i && i < n); return 2 * even[i]; }

    std::pair<int, int> odd_range(int i) const {
        assert(0 <= i && i < n);
        return {i - odd[i] + 1, i + odd[i]};
    }

    std::pair<int, int> even_range(int i) const {
        assert(0 <= i && i < n);
        return {i - even[i], i + even[i]};
    }

    int longest_length() const { return longest_right - longest_left; }
    std::pair<int, int> longest_range() const { return {longest_left, longest_right}; }
    std::string longest_palindrome() const { return s.substr(longest_left, longest_length()); }

    // 出現位置が異なる回文は別々に数える
    long long count_palindromes() const {
        long long ans = 0;
        for (int x : odd) ans += x;
        for (int x : even) ans += x;
        return ans;
    }
};

使用例 ​

cpp
Manacher ma("abacaba");

cout << ma.odd[3] << '\n';          // 4
cout << ma.odd_length(3) << '\n';   // 7
cout << ma.is_palindrome(0, 7);    // 1

cout << ma.longest_palindrome();    // abacaba
cout << ma.count_palindromes();     // 12

auto [l, r] = ma.longest_range();   // [0, 7)

偶数長回文の例。

cpp
Manacher ma("abba");

cout << ma.even[2] << '\n';         // 2
cout << ma.even_length(2) << '\n';  // 4
cout << ma.is_palindrome(0, 4);    // 1
cout << ma.count_palindromes();     // 6

主な操作 ​

メソッド機能
build(s)回文半径を再計算
odd[i]奇数長回文の半径
even[i]偶数長回文の半径
odd_length(i)奇数長回文の最大長
even_length(i)偶数長回文の最大長
odd_range(i)奇数長回文の半開区間
even_range(i)偶数長回文の半開区間
is_palindrome(l, r)区間 [l, r) の回文判定
longest_range()最長回文の半開区間
longest_length()最長回文の長さ
longest_palindrome()最長回文の文字列
count_palindromes()回文部分文字列の総数

注意点 ​

  • odd[i] は中心自身を含むため、最小値は1。
  • even[i] は中心の左右にある文字の組数で、最小値は0。
  • 区間はすべて半開区間 [l, r)。
  • 空文字列も回文として扱う。
  • 最長回文が複数ある場合は、最も左側のものを返す。
  • count_palindromes() は同じ内容でも出現位置が異なれば別々に数える。
  • longest_palindrome() は文字列をコピーするため O(回文長)。
  • この実装は char 単位で処理する。

関連 ​

  • Z-Algorithm
  • 回文
  • suffix最長回文