马拉车算法(Manacher)

1. pub fn manacher(s: String) -> String {
2. let l = s.len();
3. if l <= 1 {
4. return s;
5. }

7. // MEMO: We need to detect odd palindrome as well,
8. // therefore, inserting dummy string so that
9. // we can find a pair with dummy center character.
10. let mut chars: Vec<char> = Vec::with_capacity(s.len() * 2 + 1);
11. for c in s.chars() {
12. chars.push('#');
13. chars.push(c);
14. }
15. chars.push('#');

17. // List: storing the length of palindrome at each index of string
18. let mut length_of_palindrome = vec![1usize; chars.len()];
19. // Integer: Current checking palindrome's center index
20. let mut current_center: usize = 0;
21. // Integer: Right edge index existing the radius away from current center
22. let mut right_from_current_center: usize = 0;

24. for i in 0..chars.len() {
25. // 1: Check if we are looking at right side of palindrome.
26. if right_from_current_center > i && i > current_center {
27. // 1-1: If so copy from the left side of palindrome.
28. // If the value + index exceeds the right edge index, we should cut and check palindrome later #3.
29. length_of_palindrome[i] = std::cmp::min(
30. right_from_current_center - i,
31. length_of_palindrome[2 * current_center - i],
32. );
33. // 1-2: Move the checking palindrome to new index if it exceeds the right edge.
34. if length_of_palindrome[i] + i >= right_from_current_center {
35. current_center = i;
36. right_from_current_center = length_of_palindrome[i] + i;
37. // 1-3: If radius exceeds the end of list, it means checking is over.
38. // You will never get the larger value because the string will get only shorter.
39. if right_from_current_center >= chars.len() - 1 {
40. break;
41. }
42. } else {
43. // 1-4: If the checking index doesn't exceeds the right edge,
44. // it means the length is just as same as the left side.
45. // You don't need to check anymore.
46. continue;
47. }
48. }

50. // Integer: Current radius from checking index
51. // If it's copied from left side and more than 1,
52. // it means it's ensured so you don't need to check inside radius.
53. let mut radius: usize = (length_of_palindrome[i] - 1) / 2;
54. radius += 1;
55. // 2: Checking palindrome.
56. // Need to care about overflow usize.
57. while i >= radius && i + radius <= chars.len() - 1 && chars[i - radius] == chars[i + radius]
58. {
59. length_of_palindrome[i] += 2;
60. radius += 1;
61. }
62. }

64. // 3: Find the maximum length and generate answer.
65. let center_of_max = length_of_palindrome
66. .iter()
67. .enumerate()
68. .max_by_key(|(_, &value)| value)
69. .map(|(idx, _)| idx)
70. .unwrap();
71. let radius_of_max = (length_of_palindrome[center_of_max] - 1) / 2;
72. let answer = &chars[(center_of_max - radius_of_max)..(center_of_max + radius_of_max + 1)]
73. .iter()
74. .collect::<String>();
75. answer.replace("#", "")
76. }

78. #[cfg(test)]
79. mod tests {
80. use super::manacher;

82. #[test]
83. fn get_longest_palindrome_by_manacher() {
84. assert_eq!(manacher("babad".to_string()), "aba".to_string());
85. assert_eq!(manacher("cbbd".to_string()), "bb".to_string());
86. assert_eq!(manacher("a".to_string()), "a".to_string());

88. let ac_ans = manacher("ac".to_string());
89. assert!(ac_ans == "a".to_string() || ac_ans == "c".to_string());
90. }
91. }