马拉车算法(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. }