kmpsearch/
lib.rs

1mod tests;
2
3/// The Haystack trait is the 'target' of the KMP algorithm provided by this library.
4/// It provides the pattern_table method (part of the KMP algorithm) and the various methods for searching.
5/// Haystack is implemented on all types that can be converted to a &[u8], such as Byte slices, str and Strings.
6pub trait Haystack {
7    /// Produce a 'pattern table' for use with the Knuth Morris Pratt algorithm.
8    fn pattern_table(needle: &[u8]) -> Vec<usize> {
9        let mut i = 0;
10        let mut j = 1;
11        let mut arr = vec![0; needle.len()];
12        while j < needle.len() {
13            if needle[i] == needle[j] {
14                i += 1;
15                arr[j] = i;
16                j += 1;
17            } else {
18                if i != 0 {
19                    i = arr[i - 1];
20                } else {
21                    arr[j] = i;
22                    j += 1;
23                }
24            }
25        }
26        arr
27    }
28
29    /// Returns true if this Haystack contains needle.
30    fn contains_needle<N: AsRef<[u8]>>(&self, needle: N) -> bool;
31
32    /// Returns the first index of needle in this Haystack, or None if it doesn't contain the needle.
33    fn first_indexof_needle<N: AsRef<[u8]>>(&self, needle: N) -> Option<usize>;
34
35    /// Returns the last index of needle in this Haystack, or None if it doesn't contain the needle.
36    fn last_indexof_needle<N: AsRef<[u8]>>(&self, needle: N) -> Option<usize>;
37
38    /// Returns the last index of needle in this Haystack, or None if it doesn't contain the needle.
39    fn indexesof_needle<N: AsRef<[u8]>>(&self, needle: N) -> Option<Vec<usize>>;
40}
41
42/// Implementation allowing anything convertible to a &[u8] to use Haystack methods.
43impl<H: AsRef<[u8]>> Haystack for H {
44    fn contains_needle<N: AsRef<[u8]>>(&self, needle: N) -> bool {
45        let needle = needle.as_ref();
46        let pattern_table = Self::pattern_table(needle);
47        let haystack = &self.as_ref();
48
49        let mut haystack_c = 0usize;
50        let mut needle_c = 0usize;
51
52        let haystack_len = haystack.len();
53        let needle_len = needle.len();
54
55        while haystack_c < haystack_len {
56            if haystack[haystack_c] == needle[needle_c] {
57                haystack_c += 1;
58                needle_c += 1;
59            }
60            if needle_c == needle_len {
61                return true;
62            } else {
63                if haystack_c < haystack_len && haystack[haystack_c] != needle[needle_c] {
64                    if needle_c != 0 {
65                        needle_c = pattern_table[needle_c - 1];
66                    } else {
67                        haystack_c += 1;
68                    }
69                }
70            }
71        }
72        false
73    }
74
75    fn first_indexof_needle<N: AsRef<[u8]>>(&self, needle: N) -> Option<usize> {
76        let needle = needle.as_ref();
77        let pattern_table = Self::pattern_table(needle);
78        let haystack = &self.as_ref();
79
80        let mut haystack_c = 0usize;
81        let mut needle_c = 0usize;
82
83        let haystack_len = haystack.len();
84        let needle_len = needle.len();
85
86        while haystack_c < haystack_len {
87            if haystack[haystack_c] == needle[needle_c] {
88                haystack_c += 1;
89                needle_c += 1;
90            }
91            if needle_c == needle_len {
92                return Some(haystack_c - needle_len);
93            } else {
94                if haystack_c < haystack_len && haystack[haystack_c] != needle[needle_c] {
95                    if needle_c != 0 {
96                        needle_c = pattern_table[needle_c - 1];
97                    } else {
98                        haystack_c += 1;
99                    }
100                }
101            }
102        }
103        None
104    }
105
106    fn last_indexof_needle<N: AsRef<[u8]>>(&self, needle: N) -> Option<usize> {
107        let needle = needle.as_ref();
108        let pattern_table = Self::pattern_table(needle);
109        let haystack = &self.as_ref();
110
111        let mut haystack_c = 0usize;
112        let mut needle_c = 0usize;
113
114        let haystack_len = haystack.len();
115        let needle_len = needle.len();
116
117        let mut index: Option<usize> = None;
118
119        while haystack_c < haystack_len {
120            if haystack[haystack_c] == needle[needle_c] {
121                haystack_c += 1;
122                needle_c += 1;
123            }
124            if needle_c == needle_len {
125                index = Some(haystack_c - needle_len);
126                needle_c = 0;
127            } else {
128                if haystack_c < haystack_len && haystack[haystack_c] != needle[needle_c] {
129                    if needle_c != 0 {
130                        needle_c = pattern_table[needle_c - 1];
131                    } else {
132                        haystack_c += 1;
133                    }
134                }
135            }
136        }
137        index
138    }
139
140    fn indexesof_needle<N: AsRef<[u8]>>(&self, needle: N) -> Option<Vec<usize>> {
141        let needle = needle.as_ref();
142        let pattern_table = Self::pattern_table(needle);
143        let haystack = &self.as_ref();
144
145        let mut haystack_c = 0usize;
146        let mut needle_c = 0usize;
147
148        let haystack_len = haystack.len();
149        let needle_len = needle.len();
150
151        let mut indexes = Vec::new();
152
153        while haystack_c < haystack_len {
154            if haystack[haystack_c] == needle[needle_c] {
155                haystack_c += 1;
156                needle_c += 1;
157            }
158            if needle_c == needle_len {
159                indexes.push(haystack_c - needle_len);
160                needle_c = 0;
161            } else {
162                if haystack_c < haystack_len && haystack[haystack_c] != needle[needle_c] {
163                    if needle_c != 0 {
164                        needle_c = pattern_table[needle_c - 1];
165                    } else {
166                        haystack_c += 1;
167                    }
168                }
169            }
170        }
171        if indexes.len() > 0 {
172            Some(indexes)
173        } else {
174            None
175        }
176    }
177}
kmpsearch/lib.rs

kmpsearch/
lib.rs
