tilezz 0.2.0

//! Linear-time cyclic substring containment.

use super::period::prefix_function;

/// Returns `true` iff `needle` appears as a contiguous **cyclic**
/// substring of `haystack` — i.e. there exists some starting offset
/// `s` such that `needle[i] == haystack[(s + i) % n]` for all
/// `0 <= i < needle.len()`.
///
/// Empty needles return `false`; needles longer than `haystack` return
/// `false` (they can't fit cyclically).
///
/// O(`haystack.len()` + `needle.len()`) time via KMP run against
/// `haystack` walked cyclically for `n + m - 1` steps — that range is
/// sufficient to surface every cyclic alignment of `needle`.
pub fn cyclic_contains<T: Eq>(haystack: &[T], needle: &[T]) -> bool {
    let n = haystack.len();
    let m = needle.len();
    if m == 0 || m > n {
        return false;
    }

    let pi = prefix_function(needle);

    let total = n + m - 1;
    let mut k = 0usize;
    for i in 0..total {
        let c = &haystack[i % n];
        while k > 0 && needle[k] != *c {
            k = pi[k - 1];
        }
        if needle[k] == *c {
            k += 1;
        }
        if k == m {
            return true;
        }
    }
    false
}

/// Booth's algorithm: the index at which the lexicographically minimal rotation
/// of `s` begins, in O(n). A canonical-form primitive for cyclic words -- the
/// rotation-invariant key behind `Rat` canonicalization and the patch /
/// neighborhood / cluster canonical boundary words.
///
/// See <https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation>.
pub fn lex_min_rot<T: Eq + Ord>(s: &[T]) -> usize {
    let n = s.len() as isize;
    let mut f: Vec<isize> = vec![-1; 2 * s.len()];
    let mut k: isize = 0;
    let comp_idx = |k, i| ((k + i + 1) % n) as usize;
    for j in 1..(2 * n) {
        let j_mod_n = (j % n) as usize;
        let mut i = f[(j - k - 1) as usize];
        while i != -1 && s[j_mod_n] != s[comp_idx(k, i)] {
            if s[j_mod_n] < s[comp_idx(k, i)] {
                k = j - i - 1;
            }
            i = f[i as usize];
        }
        if i == -1 && s[j_mod_n] != s[comp_idx(k, i)] {
            if s[j_mod_n] < s[comp_idx(k, i)] {
                k = j;
            }
            f[(j - k) as usize] = -1;
        } else {
            f[(j - k) as usize] = i + 1;
        }
    }
    k as usize
}

/// The lexicographically minimal rotation of `s`, materialized as an owned
/// word -- the rotation-canonical representative of `s` up to cyclic shift.
///
/// Thin wrapper over [`lex_min_rot`] that also builds the rotated sequence. Use
/// `lex_min_rot` directly when only the start offset is wanted (e.g. to
/// re-index several parallel arrays by the same rotation); use this when the
/// canonical word itself is the key.
pub fn canonical_rotation<T: Ord + Clone>(s: &[T]) -> Vec<T> {
    let r = lex_min_rot(s);
    let n = s.len();
    (0..n).map(|i| s[(i + r) % n].clone()).collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_canonical_rotation() {
        assert_eq!(
            canonical_rotation(&['h', 'e', 'l', 'l', 'o']),
            vec!['e', 'l', 'l', 'o', 'h']
        );
        assert_eq!(canonical_rotation(&[3i8, 1, 2]), vec![1, 2, 3]);
        assert_eq!(canonical_rotation::<i8>(&[]), Vec::<i8>::new());
    }

    #[test]
    fn test_lex_min_rot() {
        assert_eq!(lex_min_rot(&['h', 'e', 'l', 'l', 'o']), 1);
        assert_eq!(lex_min_rot(&[1, 3, 2, 1, 2, 1, 2, 0]), 7);
        assert_eq!(lex_min_rot(&[1, 3, 2, 1, -2, 1, 2, 0]), 4);
        assert_eq!(lex_min_rot(&[1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1]), 10);
    }

    // Brute-force O(n*m) reference for cross-checking.
    fn naive<T: Eq>(haystack: &[T], needle: &[T]) -> bool {
        let n = haystack.len();
        let m = needle.len();
        if m == 0 || m > n {
            return false;
        }
        (0..n).any(|s| (0..m).all(|i| haystack[(s + i) % n] == needle[i]))
    }

    #[test]
    fn empty_needle_is_false() {
        assert!(!cyclic_contains::<i8>(&[1, 2, 3], &[]));
    }

    #[test]
    fn empty_haystack_is_false() {
        assert!(!cyclic_contains::<i8>(&[], &[1]));
    }

    #[test]
    fn needle_longer_than_haystack_is_false() {
        assert!(!cyclic_contains(&[1i8, 2], &[1i8, 2, 3]));
    }

    #[test]
    fn linear_substring() {
        assert!(cyclic_contains(&[1i8, 2, 3, 4, 5], &[2i8, 3, 4]));
    }

    #[test]
    fn wrapping_substring() {
        // [1,2,3,4,5] cyclically contains [4,5,1,2]
        assert!(cyclic_contains(&[1i8, 2, 3, 4, 5], &[4i8, 5, 1, 2]));
    }

    #[test]
    fn full_length_rotation() {
        // Any rotation of haystack is itself a cyclic substring at full length.
        assert!(cyclic_contains(&[1i8, 2, 3], &[3i8, 1, 2]));
        assert!(cyclic_contains(&[1i8, 2, 3], &[2i8, 3, 1]));
        assert!(cyclic_contains(&[1i8, 2, 3], &[1i8, 2, 3]));
    }

    #[test]
    fn full_length_non_rotation() {
        assert!(!cyclic_contains(&[1i8, 2, 3], &[1i8, 3, 2]));
    }

    #[test]
    fn missing_substring() {
        assert!(!cyclic_contains(&[1i8, 2, 3, 4, 5], &[2i8, 4]));
    }

    #[test]
    fn single_element_needle() {
        assert!(cyclic_contains(&[1i8, 2, 3], &[2i8]));
        assert!(!cyclic_contains(&[1i8, 2, 3], &[4i8]));
    }

    #[test]
    fn repeating_haystack() {
        // haystack is "aaaaaa", needle "aaa" — must match anywhere.
        assert!(cyclic_contains(&[1u8; 6], &[1u8; 3]));
        // haystack all-same, needle includes a different element — no.
        assert!(!cyclic_contains(&[1u8; 6], &[1u8, 1, 2]));
    }

    #[test]
    fn does_not_double_count_wrap() {
        // haystack length n, needle length n-1: only n distinct cyclic
        // starting positions are possible. None of these spuriously
        // matches a non-rotation needle.
        assert!(!cyclic_contains(&[1i8, 2, 3, 4], &[1i8, 3, 4]));
    }

    #[test]
    fn vs_naive_random() {
        let mut s: u64 = 0xc0ffee;
        let next = |state: &mut u64| {
            *state = state
                .wrapping_mul(6364136223846793005)
                .wrapping_add(1442695040888963407);
            *state
        };
        for _ in 0..500 {
            let n = (next(&mut s) as usize % 30) + 1;
            let m = (next(&mut s) as usize % (n + 2)) + 1;
            let haystack: Vec<u8> = (0..n).map(|_| (next(&mut s) % 3) as u8).collect();
            let needle: Vec<u8> = (0..m).map(|_| (next(&mut s) % 3) as u8).collect();
            assert_eq!(
                cyclic_contains(&haystack, &needle),
                naive(&haystack, &needle),
                "haystack={haystack:?} needle={needle:?}"
            );
        }
    }
}