distance-wasm 0.0.8

WebAssembly bindings for high-performance string distance and similarity algorithms
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

/// Longest Common Substring (contiguous).
///
/// Time: O(m * n), Space: O(min(m, n))

pub fn lcs_str(a: &str, b: &str) -> u32 {
    let a_bytes = a.as_bytes();
    let b_bytes = b.as_bytes();
    let a_len = a_bytes.len();
    let b_len = b_bytes.len();

    if a_len == 0 || b_len == 0 { return 0; }

    let mut max_len = 0u32;
    let mut dp = vec![0u32; b_len + 1];

    for i in 1..=a_len {
        let mut prev = 0u32;
        for j in 1..=b_len {
            let temp = dp[j];
            if a_bytes[i - 1] == b_bytes[j - 1] {
                dp[j] = prev + 1;
                if dp[j] > max_len { max_len = dp[j]; }
            } else {
                dp[j] = 0;
            }
            prev = temp;
        }
    }

    max_len
}

pub fn lcs_str_normalized(a: &str, b: &str) -> f64 {
    let max_len = a.len().max(b.len()) as f64;
    if max_len == 0.0 { return 1.0; }
    lcs_str(a, b) as f64 / max_len
}