diff options
Diffstat (limited to 'src/find.rs')
| -rw-r--r-- | src/find.rs | 232 |
1 files changed, 232 insertions, 0 deletions
diff --git a/src/find.rs b/src/find.rs new file mode 100644 index 0000000..4af3b8b --- /dev/null +++ b/src/find.rs @@ -0,0 +1,232 @@ +// The strstr implementation in this file is extracted from the Rust standard +// library's str::find. The algorithm works for arbitrary &[T] haystack and +// needle but is only exposed by the standard library on UTF-8 strings. +// +// https://github.com/rust-lang/rust/blob/1.40.0/src/libcore/str/pattern.rs +// +// --- +// +// This is the Two-Way search algorithm, which was introduced in the paper: +// Crochemore, M., Perrin, D., 1991, Two-way string-matching, Journal of the ACM 38(3):651-675. +// +// Here's some background information. +// +// A *word* is a string of symbols. The *length* of a word should be a familiar +// notion, and here we denote it for any word x by |x|. (We also allow for the +// possibility of the *empty word*, a word of length zero.) +// +// If x is any non-empty word, then an integer p with 0 < p <= |x| is said to be +// a *period* for x iff for all i with 0 <= i <= |x| - p - 1, we have x[i] == +// x[i+p]. For example, both 1 and 2 are periods for the string "aa". As another +// example, the only period of the string "abcd" is 4. +// +// We denote by period(x) the *smallest* period of x (provided that x is +// non-empty). This is always well-defined since every non-empty word x has at +// least one period, |x|. We sometimes call this *the period* of x. +// +// If u, v and x are words such that x = uv, where uv is the concatenation of u +// and v, then we say that (u, v) is a *factorization* of x. +// +// Let (u, v) be a factorization for a word x. Then if w is a non-empty word +// such that both of the following hold +// +// - either w is a suffix of u or u is a suffix of w +// - either w is a prefix of v or v is a prefix of w +// +// then w is said to be a *repetition* for the factorization (u, v). +// +// Just to unpack this, there are four possibilities here. Let w = "abc". Then +// we might have: +// +// - w is a suffix of u and w is a prefix of v. ex: ("lolabc", "abcde") +// - w is a suffix of u and v is a prefix of w. ex: ("lolabc", "ab") +// - u is a suffix of w and w is a prefix of v. ex: ("bc", "abchi") +// - u is a suffix of w and v is a prefix of w. ex: ("bc", "a") +// +// Note that the word vu is a repetition for any factorization (u,v) of x = uv, +// so every factorization has at least one repetition. +// +// If x is a string and (u, v) is a factorization for x, then a *local period* +// for (u, v) is an integer r such that there is some word w such that |w| = r +// and w is a repetition for (u, v). +// +// We denote by local_period(u, v) the smallest local period of (u, v). We +// sometimes call this *the local period* of (u, v). Provided that x = uv is +// non-empty, this is well-defined (because each non-empty word has at least one +// factorization, as noted above). +// +// It can be proven that the following is an equivalent definition of a local +// period for a factorization (u, v): any positive integer r such that x[i] == +// x[i+r] for all i such that |u| - r <= i <= |u| - 1 and such that both x[i] +// and x[i+r] are defined. (i.e., i > 0 and i + r < |x|). +// +// Using the above reformulation, it is easy to prove that +// +// 1 <= local_period(u, v) <= period(uv) +// +// A factorization (u, v) of x such that local_period(u,v) = period(x) is called +// a *critical factorization*. +// +// The algorithm hinges on the following theorem, which is stated without proof: +// +// **Critical Factorization Theorem** Any word x has at least one critical +// factorization (u, v) such that |u| < period(x). +// +// The purpose of maximal_suffix is to find such a critical factorization. +// +// If the period is short, compute another factorization x = u' v' to use for +// reverse search, chosen instead so that |v'| < period(x). + +use std::cmp; +use std::usize; + +pub fn find(haystack: &[char], needle: &[char]) -> Option<usize> { + assert!(!needle.is_empty()); + + // crit_pos: critical factorization index + let (crit_pos_false, period_false) = maximal_suffix(needle, false); + let (crit_pos_true, period_true) = maximal_suffix(needle, true); + let (crit_pos, mut period) = if crit_pos_false > crit_pos_true { + (crit_pos_false, period_false) + } else { + (crit_pos_true, period_true) + }; + + // Byteset is an extension (not part of the two way algorithm); it is a + // 64-bit "fingerprint" where each set bit j corresponds to a (byte & 63) == + // j present in the needle. + let byteset; + // Index into needle before which we have already matched. + let mut memory; + + // A particularly readable explanation of what's going on here can be found + // in Crochemore and Rytter's book "Text Algorithms", ch 13. Specifically + // see the code for "Algorithm CP" on p. 323. + // + // What's going on is we have some critical factorization (u, v) of the + // needle, and we want to determine whether u is a suffix of &v[..period]. + // If it is, we use "Algorithm CP1". Otherwise we use "Algorithm CP2", which + // is optimized for when the period of the needle is large. + let long_period = needle[..crit_pos] != needle[period..period + crit_pos]; + if long_period { + // Long period case -- we have an approximation to the actual period, + // and don't use memorization. + // + // Approximate the period by lower bound max(|u|, |v|) + 1. + period = cmp::max(crit_pos, needle.len() - crit_pos) + 1; + byteset = byteset_create(needle); + // Dummy value to signify that the period is long. + memory = usize::MAX; + } else { + // Short period case -- the period is exact. + byteset = byteset_create(&needle[..period]); + memory = 0; + } + + // One of the main ideas of Two-Way is that we factorize the needle into two + // halves, (u, v), and begin trying to find v in the haystack by scanning + // left to right. If v matches, we try to match u by scanning right to left. + // How far we can jump when we encounter a mismatch is all based on the fact + // that (u, v) is a critical factorization for the needle. + let mut position = 0; + let needle_last = needle.len() - 1; + 'search: loop { + // Check that we have room to search in. position + needle_last cannot + // overflow if we assume slices are bounded by isize's range. + let tail_byte = *haystack.get(position + needle_last)?; + + // Quickly skip by large portions unrelated to our substring. + if !byteset_contains(byteset, tail_byte) { + position += needle.len(); + if !long_period { + memory = 0; + } + continue 'search; + } + + // See if the right part of the needle matches. + let start = if long_period { + crit_pos + } else { + cmp::max(crit_pos, memory) + }; + for i in start..needle.len() { + if needle[i] != haystack[position + i] { + position += i - crit_pos + 1; + if !long_period { + memory = 0; + } + continue 'search; + } + } + + // See if the left part of the needle matches. + let start = if long_period { 0 } else { memory }; + for i in (start..crit_pos).rev() { + if needle[i] != haystack[position + i] { + position += period; + if !long_period { + memory = needle.len() - period; + } + continue 'search; + } + } + + // We have found a match! + return Some(position); + } +} + +fn byteset_create(chars: &[char]) -> u64 { + chars.iter().fold(0, |a, &ch| (1 << (ch as u8 & 0x3f)) | a) +} + +fn byteset_contains(byteset: u64, ch: char) -> bool { + (byteset >> ((ch as u8 & 0x3f) as usize)) & 1 != 0 +} + +// Compute the maximal suffix of `arr`. +// +// The maximal suffix is a possible critical factorization (u, v) of `arr`. +// +// Returns (`i`, `p`) where `i` is the starting index of v and `p` is the +// period of v. +// +// `order_greater` determines if lexical order is `<` or `>`. Both +// orders must be computed -- the ordering with the largest `i` gives +// a critical factorization. +// +// For long period cases, the resulting period is not exact (it is too short). +fn maximal_suffix(arr: &[char], order_greater: bool) -> (usize, usize) { + let mut left = 0; // Corresponds to i in the paper + let mut right = 1; // Corresponds to j in the paper + let mut offset = 0; // Corresponds to k in the paper, but starting at 0 + // to match 0-based indexing. + let mut period = 1; // Corresponds to p in the paper + + while let Some(&a) = arr.get(right + offset) { + // `left` will be inbounds when `right` is. + let b = arr[left + offset]; + if (a < b && !order_greater) || (a > b && order_greater) { + // Suffix is smaller, period is entire prefix so far. + right += offset + 1; + offset = 0; + period = right - left; + } else if a == b { + // Advance through repetition of the current period. + if offset + 1 == period { + right += offset + 1; + offset = 0; + } else { + offset += 1; + } + } else { + // Suffix is larger, start over from current location. + left = right; + right += 1; + offset = 0; + period = 1; + } + } + (left, period) +} |