haar_lib/algo/
manacher.rs

1//! Manacher's algorithm
2
3/// `s`の各要素を中心とした奇数長の最長回文の片側の長さを求める。
4///
5/// **Time complexity** $O(|s|)$
6pub fn manacher<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
28}
29
30#[cfg(test)]
31mod tests {
32    use super::*;
33
34    #[test]
35    fn test() {
36        assert_eq!(
37            manacher("abaaababa".as_bytes()),
38            [1, 2, 1, 4, 1, 2, 3, 2, 1]
39        );
40    }
41}
haar_lib/algo/manacher.rs

haar_lib/algo/
manacher.rs
