Lines Matching refs:period
73 /// corresponds to the "small period" and "large period" cases.
90 (min_suffix.period, min_suffix.pos)
92 (max_suffix.period, max_suffix.pos)
117 Shift::Small { period } => {
118 self.find_small_imp(pre, haystack, needle, period)
157 period: usize,
193 pos += period;
194 shift = needle.len() - period;
257 (min_suffix.period, min_suffix.pos)
259 (max_suffix.period, max_suffix.pos)
287 Shift::Small { period } => {
288 self.rfind_small_imp(haystack, needle, period)
315 period: usize,
341 pos -= period;
342 shift = period;
398 /// suffix, along with the period of that suffix. It turns out that the period
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
404 /// bound given here is always the period of `v`, which is `<= period(x)`. The
405 /// case where `period(v) == period(x)` occurs when `len(u) < (len(x) / 2)` and
406 /// where `u` is a suffix of `v[0..period(v)]`.
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
419 /// N.B. If we could find a way to compute the exact period in all cases,
425 Small { period: usize },
432 /// This requires a lower bound on the period and a critical position.
435 /// The lower bound on the period is then the period of the chosen suffix.
450 Shift::Small { period: period_lower_bound }
455 /// This requires a lower bound on the period and a critical position.
458 /// The lower bound on the period is then the period of the chosen suffix.
473 Shift::Small { period: period_lower_bound }
477 /// A suffix extracted from a needle along with its period.
487 /// The period of this suffix.
489 /// Note that this is NOT necessarily the period of the string from which
490 /// this suffix comes from. (It is always less than or equal to the period
492 period: usize,
500 // its period.
501 let mut suffix = Suffix { pos: 0, period: 1 };
524 suffix = Suffix { pos: candidate_start, period: 1 };
531 suffix.period = candidate_start - suffix.pos;
534 if offset + 1 == suffix.period {
535 candidate_start += suffix.period;
550 let mut suffix = Suffix { pos: needle.len(), period: 1 };
562 suffix = Suffix { pos: candidate_start, period: 1 };
569 suffix.period = suffix.pos - candidate_start;
572 if offset + 1 == suffix.period {
573 candidate_start -= suffix.period;
682 (&needle[s.pos..], s.period)
688 (&needle[..s.pos], s.period)
716 ($given:expr, $expected:expr, $period:expr) => {
720 assert_eq!(($expected, $period), (got_suffix, got_period));
725 ($given:expr, $expected:expr, $period:expr) => {
729 assert_eq!(($expected, $period), (got_suffix, got_period));
773 ($given:expr, $expected:expr, $period:expr) => {
777 assert_eq!(($expected, $period), (got_suffix, got_period));
782 ($given:expr, $expected:expr, $period:expr) => {
786 assert_eq!(($expected, $period), (got_suffix, got_period));
868 // the reverse small period handling. The bug was that we were using 'if j