path: root/src/find.rs

// 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)
}