oxihuman-core 0.1.2

Core data structures, algorithms, and asset management for OxiHuman
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
// SPDX-License-Identifier: Apache-2.0
#![allow(dead_code)]

//! Z-function string matching.

/// Compute the Z-array for string `s`.
/// `z[i]` = length of the longest substring starting at `s[i]` that is also
/// a prefix of `s`. `z[0]` is conventionally 0.
pub fn z_function(s: &[u8]) -> Vec<usize> {
    let n = s.len();
    let mut z = vec![0usize; n];
    let (mut l, mut r) = (0usize, 0usize);
    for i in 1..n {
        if i < r {
            z[i] = (r - i).min(z[i - l]);
        }
        while i + z[i] < n && s[z[i]] == s[i + z[i]] {
            z[i] += 1;
        }
        if i + z[i] > r {
            l = i;
            r = i + z[i];
        }
    }
    z
}

/// Return all positions in `text` where `pattern` starts.
pub fn z_search(text: &[u8], pattern: &[u8]) -> Vec<usize> {
    if pattern.is_empty() {
        return (0..text.len()).collect();
    }
    /* s = pattern + '$' + text */
    let mut s = Vec::with_capacity(pattern.len() + 1 + text.len());
    s.extend_from_slice(pattern);
    s.push(b'$');
    s.extend_from_slice(text);

    let z = z_function(&s);
    let plen = pattern.len();
    let offset = plen + 1;

    z.iter()
        .enumerate()
        .skip(offset)
        .filter(|(_, &v)| v == plen)
        .map(|(i, _)| i - offset)
        .collect()
}

/// Return the Z-array max value (longest prefix match at any position).
pub fn z_max(z: &[usize]) -> usize {
    z.iter().copied().max().unwrap_or(0)
}

/// Return `true` if `pattern` occurs in `text`.
pub fn z_contains(text: &[u8], pattern: &[u8]) -> bool {
    !z_search(text, pattern).is_empty()
}

/// Return the count of occurrences of `pattern` in `text`.
pub fn z_count(text: &[u8], pattern: &[u8]) -> usize {
    z_search(text, pattern).len()
}

/// Return `true` if the Z-array for `s` is consistent (all `z[i]` <= n-i).
pub fn z_valid(z: &[usize], n: usize) -> bool {
    z.iter().enumerate().all(|(i, &v)| v <= n.saturating_sub(i))
}

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

    #[test]
    fn test_z_function_basic() {
        let z = z_function(b"aabxaa");
        /* z[4] should be 2 ("aa" matches prefix) */
        assert_eq!(z[4], 2);
    }

    #[test]
    fn test_z_search_single_match() {
        let pos = z_search(b"hello world", b"world");
        assert_eq!(pos, vec![6]);
    }

    #[test]
    fn test_z_search_multiple_matches() {
        let pos = z_search(b"ababab", b"ab");
        assert_eq!(pos, vec![0, 2, 4]);
    }

    #[test]
    fn test_z_search_no_match() {
        let pos = z_search(b"hello", b"xyz");
        assert!(pos.is_empty());
    }

    #[test]
    fn test_z_contains_true() {
        assert!(z_contains(b"foobar", b"bar"));
    }

    #[test]
    fn test_z_contains_false() {
        assert!(!z_contains(b"foobar", b"baz"));
    }

    #[test]
    fn test_z_count() {
        assert_eq!(z_count(b"aaaa", b"aa"), 3);
    }

    #[test]
    fn test_z_all_same_chars() {
        let z = z_function(b"aaaa");
        /* z[1]=3, z[2]=2, z[3]=1 */
        assert_eq!(z[1], 3);
        assert_eq!(z[2], 2);
        assert_eq!(z[3], 1);
    }

    #[test]
    fn test_z_valid() {
        let s = b"abcabc";
        let z = z_function(s);
        assert!(z_valid(&z, s.len()));
    }
}