KMP算法(Knuth Morris Pratt)

  1. pub fn knuth_morris_pratt(st: String, pat: String) -> Vec<usize> {
  2.     if st.is_empty() || pat.is_empty() {
  3.         return vec![];
  4.     }
  6.     let string = st.into_bytes();
  7.     let pattern = pat.into_bytes();
  9.     // build the partial match table
  10.     let mut partial = vec![0];
  11.     for i in 1..pattern.len() {
  12.         let mut j = partial[i - 1];
  13.         while j > 0 && pattern[j] != pattern[i] {
  14.             j = partial[j - 1];
  15.         }
  16.         partial.push(if pattern[j] == pattern[i] { j + 1 } else { j });
  17.     }
  19.     // and read 'string' to find 'pattern'
  20.     let mut ret = vec![];
  21.     let mut j = 0;
  23.     for (i, &c) in string.iter().enumerate() {
  24.         while j > 0 && c != pattern[j] {
  25.             j = partial[j - 1];
  26.         }
  27.         if c == pattern[j] {
  28.             j += 1;
  29.         }
  30.         if j == pattern.len() {
  31.             ret.push(i + 1 - j);
  32.             j = partial[j - 1];
  33.         }
  34.     }
  36.     ret
  37. }
  39. #[cfg(test)]
  40. mod tests {
  41.     use super::*;
  43.     #[test]
  44.     fn each_letter_matches() {
  45.         let index = knuth_morris_pratt("aaa".to_string(), "a".to_string());
  46.         assert_eq!(index, vec![0, 1, 2]);
  47.     }
  49.     #[test]
  50.     fn a_few_separate_matches() {
  51.         let index = knuth_morris_pratt("abababa".to_string(), "ab".to_string());
  52.         assert_eq!(index, vec![0, 2, 4]);
  53.     }
  55.     #[test]
  56.     fn one_match() {
  57.         let index =
  58.             knuth_morris_pratt("ABC ABCDAB ABCDABCDABDE".to_string(), "ABCDABD".to_string());
  59.         assert_eq!(index, vec![15]);
  60.     }
  62.     #[test]
  63.     fn lots_of_matches() {
  64.         let index = knuth_morris_pratt("aaabaabaaaaa".to_string(), "aa".to_string());
  65.         assert_eq!(index, vec![0, 1, 4, 7, 8, 9, 10]);
  66.     }
  68.     #[test]
  69.     fn lots_of_intricate_matches() {
  70.         let index = knuth_morris_pratt("ababababa".to_string(), "aba".to_string());
  71.         assert_eq!(index, vec![0, 2, 4, 6]);
  72.     }
  74.     #[test]
  75.     fn not_found0() {
  76.         let index = knuth_morris_pratt("abcde".to_string(), "f".to_string());
  77.         assert_eq!(index, vec![]);
  78.     }
  80.     #[test]
  81.     fn not_found1() {
  82.         let index = knuth_morris_pratt("abcde".to_string(), "ac".to_string());
  83.         assert_eq!(index, vec![]);
  84.     }
  86.     #[test]
  87.     fn not_found2() {
  88.         let index = knuth_morris_pratt("ababab".to_string(), "bababa".to_string());
  89.         assert_eq!(index, vec![]);
  90.     }
  92.     #[test]
  93.     fn empty_string() {
  94.         let index = knuth_morris_pratt("".to_string(), "abcdef".to_string());
  95.         assert_eq!(index, vec![]);
  96.     }
  97. }