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. }