Algod/string/
rabin_karp.rs

1pub 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    }
6
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());
13
14        if string_hash == hash_pattern && s == string {
15            ret.push(i);
16        }
17    }
18    ret
19}
20
21fn 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}
37
38#[cfg(test)]
39mod tests {
40    use super::*;
41
42    #[test]
43    fn hi_hash() {
44        let hash_result = hash("hi".to_string());
45        assert_eq!(hash_result, 65);
46    }
47
48    #[test]
49    fn abr_hash() {
50        let hash_result = hash("abr".to_string());
51        assert_eq!(hash_result, 4);
52    }
53
54    #[test]
55    fn bra_hash() {
56        let hash_result = hash("bra".to_string());
57        assert_eq!(hash_result, 30);
58    }
59
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    }
66
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    }
72
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    }
78
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    }
84
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    }
90
91    #[test]
92    fn not_found0() {
93        let index = rabin_karp("abcde".to_string(), "f".to_string());
94        assert_eq!(index, vec![]);
95    }
96
97    #[test]
98    fn not_found1() {
99        let index = rabin_karp("abcde".to_string(), "ac".to_string());
100        assert_eq!(index, vec![]);
101    }
102
103    #[test]
104    fn not_found2() {
105        let index = rabin_karp("ababab".to_string(), "bababa".to_string());
106        assert_eq!(index, vec![]);
107    }
108
109    #[test]
110    fn empty_string() {
111        let index = rabin_karp("".to_string(), "abcdef".to_string());
112        assert_eq!(index, vec![]);
113    }
114}
Algod/string/rabin_karp.rs

Algod/string/
rabin_karp.rs
