haar_lib/algo/
manacher.rs

1//! Manacher's algorithm
2
3/// `s`の各要素を中心とした奇数長の最長回文の長さを求める。
4///
5/// **Time complexity** $O(|s|)$
6pub fn manacher_odd<T: PartialEq>(s: &[T]) -> Vec<usize> {
7    let n = s.len();
8    let mut ret = vec![0; n];
9    let mut center = 0;
10
11    for cur in 0..n {
12        let left: i32 = center as i32 * 2 - cur as i32;
13
14        if left >= 0 && cur + ret[left as usize] < center + ret[center] {
15            ret[cur] = ret[left as usize];
16        } else {
17            let mut len = center + ret[center] - cur;
18            while cur >= len && cur + len < n && s[cur - len] == s[cur + len] {
19                len += 1;
20            }
21
22            ret[cur] = len;
23            center = cur;
24        }
25    }
26
27    ret.into_iter().map(|l| l * 2 - 1).collect()
28}
29
30/// `s`の各要素の間を中心とした偶数長の最長回文の長さを求める。
31///
32/// **Time complexity** $O(|s|)$
33pub fn manacher_even<T: PartialEq>(s: &[T]) -> Vec<usize> {
34    let n = s.len();
35    let mut t = vec![None; n * 2 - 1];
36
37    for (i, a) in s.iter().enumerate() {
38        t[i * 2] = Some(a);
39    }
40
41    manacher_odd(&t)
42        .into_iter()
43        .skip(1)
44        .step_by(2)
45        .map(|l| (l / 2).div_ceil(2) * 2)
46        .collect()
47}
48
49/// [`manacher_odd`]と[`manacher_even`]の結果を回文の中心位置の順に並べたものを返す。
50///
51/// **Time complexity** $O(|s|)$
52pub fn manacher<T: PartialEq>(s: &[T]) -> Vec<usize> {
53    let n = s.len();
54    let mut odd = manacher_odd(s).into_iter();
55    let mut even = manacher_even(s).into_iter();
56
57    let mut ret = vec![];
58
59    for _ in 0..n - 1 {
60        ret.push(odd.next().unwrap());
61        ret.push(even.next().unwrap());
62    }
63    ret.push(odd.next().unwrap());
64    ret
65}
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test() {
73        assert_eq!(
74            manacher_odd("abaaababa".as_bytes()),
75            [1, 3, 1, 7, 1, 3, 5, 3, 1]
76        );
77        assert_eq!(
78            manacher_even("abaaababa".as_bytes()),
79            [0, 0, 2, 2, 0, 0, 0, 0]
80        );
81
82        assert_eq!(manacher("aaaaa".as_bytes()), [1, 2, 3, 4, 5, 4, 3, 2, 1]);
83    }
84}
haar_lib/algo/manacher.rs

haar_lib/algo/
manacher.rs
