1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/// Manarcher algorithm
///
/// Manacher's algorithm uses the symmetry of palindromes to avoid redundant comparisons, achieving linear time. It transforms the input to handle both odd- and even-length palindromes uniformly.
///
/// # Examples
///
/// Basic usage:
/// ```
/// let result = algorithmz::string::manarcher("babad");
/// assert_eq!(result, String::from("aba"));
/// ```
pub fn manarcher(s: &str) -> String {
let t = format!(
"^#{}#$",
s.chars()
.map(|c| c.to_string())
.collect::<Vec<_>>()
.join("#")
);
let t_chars: Vec<char> = t.chars().collect();
let n = t_chars.len();
let mut p = vec![0usize; n];
let mut center = 0usize;
let mut right = 0usize;
for i in 1..n - 1 {
let mirror = 2 * center as isize - i as isize;
if i < right {
p[i] = p[mirror as usize].min(right - i);
}
while t_chars[i + p[i] + 1] == t_chars[i - p[i] - 1] {
p[i] += 1;
}
if i + p[i] > right {
center = i;
right = i + p[i];
}
}
let (center_index, &max_len) = p
.iter()
.enumerate()
.max_by_key(|&(_, v)| v)
.unwrap();
let start = (center_index - max_len) / 2;
s.chars()
.skip(start)
.take(max_len)
.collect()
}