competitive_library/string/
manacher.rs

1pub fn manacher(s: &[char]) -> Vec<usize> {
2    let (mut radius, mut i, mut j) = (vec![0; s.len()], 0, 0);
3    while i < s.len() {
4        while i >= j && i + j < s.len() && s[i - j] == s[i + j] {
5            j += 1;
6        }
7        radius[i] = j;
8        let mut k = 1;
9        while i >= k && k + radius[i - k] < j {
10            radius[i + k] = radius[i - k];
11            k += 1;
12        }
13        i += k;
14        j -= k;
15    }
16    radius
17}
18
19#[deprecated(since = "0.1.0", note = "use `manacher` instead")]
20pub use manacher as manachar;
21
22#[cfg(test)]
23mod tests {
24    use super::*;
25    #[test]
26    fn a() {
27        assert_eq!(
28            manacher(&to_v("qwertyuiop")),
29            [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
30        );
31        assert_eq!(
32            manacher(&to_v("qwertyuiopoiuytrewq")),
33            [1, 1, 1, 1, 1, 1, 1, 1, 1, 10, 1, 1, 1, 1, 1, 1, 1, 1, 1]
34        );
35        assert_eq!(
36            manacher(&to_v("qwqwqwqwqwqwq")),
37            [1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 3, 2, 1]
38        );
39        assert_eq!(manacher(&to_v("abaaababa")), [1, 2, 1, 4, 1, 2, 3, 2, 1]);
40        assert_eq!(
41            manacher(&to_v("aaaaaaaaaa")),
42            [1, 2, 3, 4, 5, 5, 4, 3, 2, 1]
43        );
44    }
45
46    fn to_v(s: &str) -> Vec<char> {
47        String::from(s).chars().collect::<Vec<_>>()
48    }
49}
competitive_library/string/manacher.rs

competitive_library/string/
manacher.rs
