lzcomplexity_core/
lpf.rs

1//! Longest Previous Factor — port of `lz::utils::LPF` from modules/core/src/lpf.cpp.
2//!
3//! For each position i in the sequence, lpf[i] is the length of the longest
4//! factor starting at i that also occurs earlier in the sequence. The C++
5//! implementation operates on the SA / LCP arrays via a stack of (len, pos).
6
7/// Compute the LPF array. `lpf` must already be sized to `n`.
8pub fn lpf(lpf_out: &mut [u32], mut sa: Vec<u32>, mut lcp_in: Vec<u32>, n: usize) {
9    debug_assert!(lpf_out.len() >= n);
10    if n == 0 {
11        return;
12    }
13    if n == 1 {
14        lpf_out[0] = 0;
15        return;
16    }
17
18    // The C++ pushes a 0 sentinel onto SA and LCP, indexing up to i == n.
19    sa.push(0);
20    lcp_in.push(0);
21
22    // Stack of (len, pos). pos here matches the C++ semantics: SA[i] + 1.
23    let mut stack: Vec<(u32, u32)> = Vec::new();
24    stack.push((0, sa[0] + 1));
25
26    for i in 1..=n {
27        let mut lcp = lcp_in[i];
28        while let Some(&(top_len, top_pos)) = stack.last() {
29            if sa[i] + 1 >= top_pos {
30                break;
31            }
32            // lpf[top_pos - 1] = max(top_len, lcp); lcp = min(top_len, lcp); stack.pop()
33            let target = (top_pos - 1) as usize;
34            if target < lpf_out.len() {
35                lpf_out[target] = top_len.max(lcp);
36            }
37            lcp = top_len.min(lcp);
38            stack.pop();
39        }
40        if i < n {
41            stack.push((lcp, sa[i] + 1));
42        }
43    }
44}
45
46#[cfg(test)]
47mod tests {
48    use super::*;
49    use crate::suffix_array::{build_lcp, build_suffix_array};
50
51    #[test]
52    fn lpf_banana() {
53        let text = b"banana";
54        let sa = build_suffix_array(text);
55        let lcp = build_lcp(text, &sa);
56        let mut out = vec![0u32; text.len()];
57        lpf(&mut out, sa, lcp, text.len());
58        // Reasonable smoke test: the LZ76 walk over this must produce
59        // a non-empty factor list (validated indirectly in lz76 tests).
60        assert_eq!(out.len(), 6);
61    }
62}
lzcomplexity_core/lpf.rs

lzcomplexity_core/
lpf.rs
