Lines Matching refs:needle
7 to compute a needle hash and zip through the haystack when compared to
17 requires space proportional to the alphabet and the needle. If we, for
34 /// Whether RK is believed to be very fast for the given needle/haystack.
39 /// Search for the first occurrence of needle in haystack using Rabin-Karp.
40 pub(crate) fn find(haystack: &[u8], needle: &[u8]) -> Option<usize> {
41 find_with(&NeedleHash::forward(needle), haystack, needle)
44 /// Search for the first occurrence of needle in haystack using Rabin-Karp with
45 /// a pre-computed needle hash.
49 needle: &[u8],
51 if haystack.len() < needle.len() {
55 let mut hash = Hash::from_bytes_fwd(&haystack[..needle.len()]);
59 if nhash.eq(hash) && is_prefix(haystack, needle) {
62 if needle.len() >= haystack.len() {
65 hash.roll(&nhash, haystack[0], haystack[needle.len()]);
70 /// Search for the last occurrence of needle in haystack using Rabin-Karp.
71 pub(crate) fn rfind(haystack: &[u8], needle: &[u8]) -> Option<usize> {
72 rfind_with(&NeedleHash::reverse(needle), haystack, needle)
75 /// Search for the last occurrence of needle in haystack using Rabin-Karp with
76 /// a pre-computed needle hash.
80 needle: &[u8],
82 if haystack.len() < needle.len() {
86 Hash::from_bytes_rev(&haystack[haystack.len() - needle.len()..]);
88 if nhash.eq(hash) && is_suffix(haystack, needle) {
89 return Some(haystack.len() - needle.len());
91 if needle.len() >= haystack.len() {
97 haystack[haystack.len() - needle.len() - 1],
103 /// A hash derived from a needle.
110 /// where n is the length of the needle. This is how we "remove" a byte
116 /// Create a new Rabin-Karp hash for the given needle for use in forward
118 pub(crate) fn forward(needle: &[u8]) -> NeedleHash {
120 if needle.is_empty() {
123 nh.hash.add(needle[0]);
124 for &b in needle.iter().skip(1) {
131 /// Create a new Rabin-Karp hash for the given needle for use in reverse
133 pub(crate) fn reverse(needle: &[u8]) -> NeedleHash {
135 if needle.is_empty() {
138 nh.hash.add(needle[needle.len() - 1]);
139 for &b in needle.iter().rev().skip(1) {
152 /// A Rabin-Karp hash. This might represent the hash of a needle, or the hash
181 /// Add 'new' and remove 'old' from this hash. The given needle hash should
182 /// correspond to the hash computed for the needle being searched for.
196 /// Remove a byte from this hash. The given needle hash should correspond
197 /// to the hash computed for the needle being searched for.
204 /// Returns true if the given needle is a prefix of the given haystack.
212 fn is_prefix(haystack: &[u8], needle: &[u8]) -> bool {
213 crate::memmem::util::is_prefix(haystack, needle)
216 /// Returns true if the given needle is a suffix of the given haystack.
221 fn is_suffix(haystack: &[u8], needle: &[u8]) -> bool {
222 crate::memmem::util::is_suffix(haystack, needle)