Manacher（回文半径）

string/manacher.hpp · GitHub で見る

共通ページ

各位置を中心とする最長の回文を線形時間で求めます。前計算後は、任意の区間が回文かを定数時間で判定できます。

#include "lib/string/manacher.hpp"

Manacher palindrome("abacabba");
assert(palindrome.odd[1] == 2);  // "aba"
assert(palindrome.even[6] == 2); // "abba"
assert(palindrome.is_palindrome(4, 8));
auto [l, r] = palindrome.longest_palindrome(); // [1,6): "bacab"
auto count = palindrome.palindrome_count();   // 13 (int64_t)
auto lengths = Manacher("aba").lengths();    // {1,0,3,0,1}

std::vector<int> a = {10, -3, -3, 10};
Manacher sequence(a);
assert(sequence.is_palindrome(0, 4));

添字は 0 始まり、区間は半開区間 [l,r) です。odd[i] は中心 i を含めた片側の長さ、even[i] は i-1 と i の間を中心とする片側の長さです。

半径	最長の回文の区間	長さ
odd[i] = k	[i-k+1,i+k)	\(2k-1\)
even[i] = k	[i-k,i+k)	\(2k\)

操作・メンバー	内容・返り値	計算量
Manacher(s) / build(s)	列 s の回文半径を構築／再構築	\(O(n)\)
odd[i] / even[i]	奇数長／偶数長の回文半径	\(O(1)\)
is_palindrome(l,r)	[l,r) が回文か。空区間も true	\(O(1)\)
longest_palindrome()	最長の回文の [l,r) を pair<int,int> で返す。同長なら開始位置が最小のもの	\(O(n)\)
palindrome_count()	空でない回文の出現数を int64_t で返す。同じ文字列でも位置が異なれば別に数える	\(O(n)\)
lengths()	文字・文字間の中心を左から並べた最長回文長の vector<int>	\(O(n)\)
size() / empty()	入力の長さ／空か	\(O(1)\)

std::string・std::string_view・文字列リテラルのほか、size()・添字アクセス・要素の等値比較が使える vector・array・span などを渡せます。これらの操作は定数時間とします。入力は保持しないので、構築後に変更・破棄して構いません。公開配列 odd・even は直接書き換えないでください。

空列にも対応し、最長回文は [0,0)、出現数は 0、lengths() は空配列になります。文字列はバイト単位で扱い、NUL を含む全てのバイトに対応します。埋め込み NUL は長さを指定した string_view または string で渡してください。入力長は INT_MAX 以下とします。

入力長を \(n\) とすると、構築は \(O(n)\) 時間・空間、区間の回文判定は \(O(1)\) 時間です。

検証コード

• test/enumerate_palindromes.test.cpp

コード

#ifndef MANACHER_HPP
#define MANACHER_HPP

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <limits>
#include <string_view>
#include <utility>
#include <vector>

class Manacher {
  public:
	std::vector<int> odd, even;

	Manacher() = default;
	explicit Manacher(std::string_view s) { build(s); }
	template <class Sequence> requires requires(const Sequence &s) { s.size(); s[0]; }
	explicit Manacher(const Sequence &s) { build(s); }
	void build(std::string_view s) { build<std::string_view>(s); }
	template <class Sequence> requires requires(const Sequence &s) { s.size(); s[0]; }
	void build(const Sequence &s) {
		assert(s.size() <= std::size_t(std::numeric_limits<int>::max()));
		int n = int(s.size());
		odd.resize(n), even.resize(n);
		int first = std::min(n, 1);
		while (first < n && s[first] == s[0]) ++first;
		for (int i = 0; i < first; ++i) {
			odd[i] = std::min(i + 1, first - i);
			even[i] = std::min(i, first - i);
		}
		for (int i = first, k = 1; i < n;) {
			int limit = std::min(i + 1, n - i);
			while (k < limit && s[i - k] == s[i + k]) ++k;
			odd[i] = k;
			int j = 1;
			while (j < k && odd[i - j] != k - j) {
				odd[i + j] = std::min(odd[i - j], k - j);
				++j;
			}
			i += j;
			k = std::max(k - j, 1);
		}
		for (int i = first, k = 0; i < n;) {
			int limit = std::min(i, n - i);
			while (k < limit && s[i - k - 1] == s[i + k]) ++k;
			even[i] = k;
			int j = 1;
			while (j < k && even[i - j] != k - j) {
				even[i + j] = std::min(even[i - j], k - j);
				++j;
			}
			i += j;
			k = std::max(k - j, 0);
		}
	}
	int size() const { return int(odd.size()); }
	bool empty() const { return odd.empty(); }
	bool is_palindrome(int l, int r) const {
		assert(0 <= l && l <= r && r <= size());
		int length = r - l, center = l + length / 2;
		return !length || (length & 1 ? odd[center] > length / 2 : even[center] >= length / 2);
	}
	std::pair<int, int> longest_palindrome() const {
		int start = 0, length = 0;
		for (int i = 0; i < size(); ++i) {
			int a = 2 * (odd[i] - 1) + 1, b = 2 * even[i];
			if (a > length) start = i - odd[i] + 1, length = a;
			if (b > length) start = i - even[i], length = b;
		}
		return {start, start + length};
	}
	std::int64_t palindrome_count() const {
		std::int64_t result = 0;
		for (int i = 0; i < size(); ++i) result += std::int64_t(odd[i]) + even[i];
		return result;
	}
	std::vector<int> lengths() const {
		if (empty()) return {};
		std::vector<int> result(2 * odd.size() - 1);
		for (int i = 0; i < size(); ++i) {
			result[2 * std::size_t(i)] = 2 * (odd[i] - 1) + 1;
			if (i) result[2 * std::size_t(i) - 1] = 2 * even[i];
		}
		return result;
	}
};

#endif

Back to top page