Lines Matching refs:needle
18 /// `n ~ len(needle)` and `m ~ len(haystack)`.
25 /// (3) this will detect bytes that are believed to be rare in the needle and
39 /// 1) Do something to detect a "critical" position in the needle.
40 /// 2) For the current position in the haystack, look if needle[critical..]
42 /// 3) If so, look if needle[..critical] matches.
52 /// for any b in the needle.
56 /// position (the length of the needle). This is essentially the shift
58 /// in the needle.
63 /// A critical position in needle. Specifically, this position corresponds
64 /// to beginning of either the minimal or maximal suffix in needle. (N.B.
80 pub(crate) fn new(needle: &[u8]) -> Forward {
81 if needle.is_empty() {
85 let byteset = ApproximateByteSet::new(needle);
86 let min_suffix = Suffix::forward(needle, SuffixKind::Minimal);
87 let max_suffix = Suffix::forward(needle, SuffixKind::Maximal);
94 let shift = Shift::forward(needle, period_lower_bound, critical_pos);
98 /// Find the position of the first occurrence of this searcher's needle in
104 /// Callers must guarantee that the needle is non-empty and its length is
111 needle: &[u8],
113 debug_assert!(!needle.is_empty(), "needle should not be empty");
114 debug_assert!(needle.len() <= haystack.len(), "haystack too short");
118 self.find_small_imp(pre, haystack, needle, period)
121 self.find_large_imp(pre, haystack, needle, shift)
134 needle: &[u8],
136 if needle.is_empty() {
138 } else if haystack.len() < needle.len() {
141 self.find(pre, haystack, needle)
156 needle: &[u8],
159 let last_byte = needle.len() - 1;
162 while pos + needle.len() <= haystack.len() {
166 pos += pre.call(&haystack[pos..], needle)?;
169 if pos + needle.len() > haystack.len() {
175 pos += needle.len();
179 while i < needle.len() && needle[i] == haystack[pos + i] {
182 if i < needle.len() {
187 while j > shift && needle[j] == haystack[pos + j] {
190 if j <= shift && needle[shift] == haystack[pos + shift] {
194 shift = needle.len() - period;
205 needle: &[u8],
208 let last_byte = needle.len() - 1;
210 'outer: while pos + needle.len() <= haystack.len() {
213 pos += pre.call(&haystack[pos..], needle)?;
214 if pos + needle.len() > haystack.len() {
221 pos += needle.len();
225 while i < needle.len() && needle[i] == haystack[pos + i] {
228 if i < needle.len() {
232 if needle[j] != haystack[pos + j] {
247 pub(crate) fn new(needle: &[u8]) -> Reverse {
248 if needle.is_empty() {
252 let byteset = ApproximateByteSet::new(needle);
253 let min_suffix = Suffix::reverse(needle, SuffixKind::Minimal);
254 let max_suffix = Suffix::reverse(needle, SuffixKind::Maximal);
261 // let critical_pos = needle.len() - critical_pos;
262 let shift = Shift::reverse(needle, period_lower_bound, critical_pos);
266 /// Find the position of the last occurrence of this searcher's needle
272 /// Callers must guarantee that the needle is non-empty and its length is
278 needle: &[u8],
280 debug_assert!(!needle.is_empty(), "needle should not be empty");
281 debug_assert!(needle.len() <= haystack.len(), "haystack too short");
288 self.rfind_small_imp(haystack, needle, period)
291 self.rfind_large_imp(haystack, needle, shift)
300 fn rfind_general(&self, haystack: &[u8], needle: &[u8]) -> Option<usize> {
301 if needle.is_empty() {
303 } else if haystack.len() < needle.len() {
306 self.rfind(haystack, needle)
314 needle: &[u8],
317 let nlen = needle.len();
327 while i > 0 && needle[i - 1] == haystack[pos - nlen + i - 1] {
330 if i > 0 || needle[0] != haystack[pos - nlen] {
335 while j < shift && needle[j] == haystack[pos - nlen + j] {
352 needle: &[u8],
355 let nlen = needle.len();
363 while i > 0 && needle[i - 1] == haystack[pos - nlen + i - 1] {
366 if i > 0 || needle[0] != haystack[pos - nlen] {
370 while j < nlen && needle[j] == haystack[pos - nlen + j] {
396 /// When computing a critical factorization of the needle, we find the position
397 /// of the critical factorization by finding the needle's maximal (or minimal)
399 /// of that suffix is a lower bound on the period of the needle itself.
401 /// This lower bound is equivalent to the actual period of the needle in
402 /// some cases. To describe that case, we denote the needle as `x` where
411 /// equivalent, we know that the period of the needle is no less than half its
413 /// period of the needle (determined by the maximum length of the components
430 /// Compute the shift for a given needle in the forward direction.
437 needle: &[u8],
441 let large = cmp::max(critical_pos, needle.len() - critical_pos);
442 if critical_pos * 2 >= needle.len() {
446 let (u, v) = needle.split_at(critical_pos);
453 /// Compute the shift for a given needle in the reverse direction.
460 needle: &[u8],
464 let large = cmp::max(critical_pos, needle.len() - critical_pos);
465 if (needle.len() - critical_pos) * 2 >= needle.len() {
469 let (v, u) = needle.split_at(critical_pos);
477 /// A suffix extracted from a needle along with its period.
496 fn forward(needle: &[u8], kind: SuffixKind) -> Suffix {
497 debug_assert!(!needle.is_empty());
502 // The start of a suffix in `needle` that we are considering as a
519 while candidate_start + offset < needle.len() {
520 let current = needle[suffix.pos + offset];
521 let candidate = needle[candidate_start + offset];
546 fn reverse(needle: &[u8], kind: SuffixKind) -> Suffix {
547 debug_assert!(!needle.is_empty());
550 let mut suffix = Suffix { pos: needle.len(), period: 1 };
551 if needle.len() == 1 {
554 let mut candidate_start = needle.len() - 1;
558 let current = needle[suffix.pos - offset - 1];
559 let candidate = needle[candidate_start - offset - 1];
641 /// A bitset used to track whether a particular byte exists in a needle or not.
644 /// needle. If a particular byte in the haystack is NOT in this set, then one
645 /// can conclude that it is also not in the needle, and thus, one can advance
646 /// in the haystack by needle.len() bytes.
651 /// Create a new set from the given needle.
652 fn new(needle: &[u8]) -> ApproximateByteSet {
654 for &b in needle {
680 fn get_suffix_forward(needle: &[u8], kind: SuffixKind) -> (&[u8], usize) {
681 let s = Suffix::forward(needle, kind);
682 (&needle[s.pos..], s.period)
686 fn get_suffix_reverse(needle: &[u8], kind: SuffixKind) -> (&[u8], usize) {
687 let s = Suffix::reverse(needle, kind);
688 (&needle[..s.pos], s.period)
697 fn naive_maximal_suffix_forward(needle: &[u8]) -> &[u8] {
698 let mut sufs = suffixes(needle);
705 fn naive_maximal_suffix_reverse(needle: &[u8]) -> Vec<u8> {
706 let mut reversed = needle.to_vec();
853 needle: &[u8],
855 Forward::new(needle).find_general(None, haystack, needle)
860 needle: &[u8],
862 Reverse::new(needle).rfind_general(haystack, needle)
875 let needle = "abab";
876 assert_eq!(Some(0), rfind(haystack.as_bytes(), needle.as_bytes()));