Rabin Karp算法

  1. pub fn rabin_karp(target: String, pattern: String) -> Vec<usize> {
  2.     // Quick exit
  3.     if target.is_empty() || pattern.is_empty() || pattern.len() > target.len() {
  4.         return vec![];
  5.     }
  7.     let string: String = (&pattern[0..pattern.len()]).to_string();
  8.     let hash_pattern = hash(string.clone());
  9.     let mut ret = vec![];
  10.     for i in 0..(target.len() - pattern.len() + 1) {
  11.         let s = (&target[i..(i + pattern.len())]).to_string();
  12.         let string_hash = hash(s.clone());
  14.         if string_hash == hash_pattern && s == string {
  15.             ret.push(i);
  16.         }
  17.     }
  18.     ret
  19. }
  21. fn hash(mut s: String) -> u16 {
  22.     let prime: u16 = 101;
  23.     let last_char = s
  24.         .drain(s.len() - 1..)
  25.         .next()
  26.         .expect("Failed to get the last char of the string");
  27.     let mut res: u16 = 0;
  28.     for (i, &c) in s.as_bytes().iter().enumerate() {
  29.         if i == 0 {
  30.             res = (c as u16 * 256) % prime;
  31.         } else {
  32.             res = (((res + c as u16) % 101) * 256) % 101;
  33.         }
  34.     }
  35.     (res + last_char as u16) % prime
  36. }
  38. #[cfg(test)]
  39. mod tests {
  40.     use super::*;
  42.     #[test]
  43.     fn hi_hash() {
  44.         let hash_result = hash("hi".to_string());
  45.         assert_eq!(hash_result, 65);
  46.     }
  48.     #[test]
  49.     fn abr_hash() {
  50.         let hash_result = hash("abr".to_string());
  51.         assert_eq!(hash_result, 4);
  52.     }
  54.     #[test]
  55.     fn bra_hash() {
  56.         let hash_result = hash("bra".to_string());
  57.         assert_eq!(hash_result, 30);
  58.     }
  60.     // Attribution to @pgimalac for his tests from Knuth-Morris-Pratt
  61.     #[test]
  62.     fn each_letter_matches() {
  63.         let index = rabin_karp("aaa".to_string(), "a".to_string());
  64.         assert_eq!(index, vec![0, 1, 2]);
  65.     }
  67.     #[test]
  68.     fn a_few_separate_matches() {
  69.         let index = rabin_karp("abababa".to_string(), "ab".to_string());
  70.         assert_eq!(index, vec![0, 2, 4]);
  71.     }
  73.     #[test]
  74.     fn one_match() {
  75.         let index = rabin_karp("ABC ABCDAB ABCDABCDABDE".to_string(), "ABCDABD".to_string());
  76.         assert_eq!(index, vec![15]);
  77.     }
  79.     #[test]
  80.     fn lots_of_matches() {
  81.         let index = rabin_karp("aaabaabaaaaa".to_string(), "aa".to_string());
  82.         assert_eq!(index, vec![0, 1, 4, 7, 8, 9, 10]);
  83.     }
  85.     #[test]
  86.     fn lots_of_intricate_matches() {
  87.         let index = rabin_karp("ababababa".to_string(), "aba".to_string());
  88.         assert_eq!(index, vec![0, 2, 4, 6]);
  89.     }
  91.     #[test]
  92.     fn not_found0() {
  93.         let index = rabin_karp("abcde".to_string(), "f".to_string());
  94.         assert_eq!(index, vec![]);
  95.     }
  97.     #[test]
  98.     fn not_found1() {
  99.         let index = rabin_karp("abcde".to_string(), "ac".to_string());
  100.         assert_eq!(index, vec![]);
  101.     }
  103.     #[test]
  104.     fn not_found2() {
  105.         let index = rabin_karp("ababab".to_string(), "bababa".to_string());
  106.         assert_eq!(index, vec![]);
  107.     }
  109.     #[test]
  110.     fn empty_string() {
  111.         let index = rabin_karp("".to_string(), "abcdef".to_string());
  112.         assert_eq!(index, vec![]);
  113.     }
  114. }