pub fn manacher<T: Eq + Clone>(sequence: &[T]) -> Vec<usize>Expand description
Manacher 法で奇数長・偶数長の回文半径をまとめて返します。
戻り値の長さは 2 * sequence.len() + 1 です。空の入力では [1] を返します。
偶数添字は要素間、奇数添字は元の要素を
中心とします。radii[i] は区切りを挿入した列上で中心自身を含む半径であり、対応する
元の回文長は radii[i] - 1 です。元の列の添字における回文の開始位置は、中心 i と半径 r
から (i + 1 - r) / 2 で求められます。N = sequence.len() とすると、計算量と追加メモリは O(N) です。
§Examples
use atcoder::string::manacher;
let radii = manacher(&['a', 'b', 'b', 'a']);
assert_eq!(radii[4] - 1, 4);