Manacher
クラス · Manacher
template <typename Container>
struct Manacher;
概要
Manacher
R[i] := S[i-R[i]:i] == S[i:i+R[i]]
計算量
- 構築は $O(n)$、参照は $O(1)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
列sの各中心の回文半径を構築する | $O(n)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
begin |
半径列の先頭iteratorを返す | $O(1)$ |
end |
半径列の終端iteratorを返す | $O(1)$ |
get |
回文半径列を返す | $O(1)$ |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator[] |
(1) 中心iの回文半径を返す (2) 中心iの回文半径を変更可能な参照で返す |
$O(1)$ |
メンバの詳細
begin
// (1)
const auto begin() const;
// (2)
auto begin();
(1)、(2) 半径列の先頭iteratorを返す
- 計算量: $O(1)$
end
// (1)
const auto end() const;
// (2)
auto end();
(1)、(2) 半径列の終端iteratorを返す
- 計算量: $O(1)$
operator[]
// (1)
const auto &operator[](int i) const;
// (2)
auto &operator[](int i);
(1) 中心iの回文半径を返す
- 計算量: $O(1)$
(2) 中心iの回文半径を変更可能な参照で返す
- 計算量: $O(1)$