lcs_rs 0.1.1

Implementation of the longest common subsequence
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
132
133
134

//! This crate calculates [the longest common subsequence](https://en.wikipedia.org/wiki/Longest_common_subsequence)

use std::{cmp::max, fmt::Debug};

#[cfg(test)]
mod test_format;

#[inline]
fn fill_matrice(s1: &str, s2: &str) -> Vec<Vec<usize>> {
    let size_s1 = s1.chars().count() + 1;
    let size_s2 = s2.chars().count() + 1;

    let mut mat: Vec<Vec<usize>> = vec![vec![0; size_s2]; size_s1];

    let mut s1_iter = s1.chars();
    let mut u = None;

    for i in 0..size_s1 {
        let mut s2_iter = s2.chars();
        let mut v = None;

        for j in 0..size_s2 {
            if i == 0 || j == 0 {
                mat[i][j] = 0;
            } else if u.unwrap() == v.unwrap() {
                mat[i][j] = mat[i - 1][j - 1] + 1;
            } else {
                mat[i][j] = max(mat[i - 1][j], mat[i][j - 1]);
            }
            v = s2_iter.next();
        }
        u = s1_iter.next();
    }
    mat
}

/// Return the lenght of the longest common subsequence between s1 and s2
/// ```
/// let s1 = "GCACAGCGGT";
/// let s2 = "TTGTGAAATC";
///
/// assert!(lcs_rs::lcs_len(s1, s2) == 4);
/// ```
#[must_use]
pub fn lcs_len(s1: &str, s2: &str) -> usize {
    let mat = fill_matrice(s1, s2);
    mat[s1.len()][s2.len()]
}

/// Return the longest common subsequence between s1 and s2
/// ```
/// let s1 = "GCACAGCGGT";
/// let s2 = "TTGTGAAATC";
///
/// assert!(lcs_rs::lcs(s1, s2) == "GAAT");
/// ```
#[must_use]
pub fn lcs(s1: &str, s2: &str) -> String {
    let mat = fill_matrice(s1, s2);

    let mut res = String::new();

    let mut s1_iter = s1.chars().rev().peekable();
    let mut s2_iter = s2.chars().rev().peekable();

    let mut i = s1.len();
    let mut j = s2.len();

    while i > 0 && j > 0 {
        if s1_iter.peek().unwrap() == s2_iter.peek().unwrap() {
            res.insert(0, *s1_iter.peek().unwrap());
            s1_iter.next();
            s2_iter.next();
            i -= 1;
            j -= 1;
        } else if mat[i - 1][j] > mat[i][j - 1] {
            s1_iter.next();
            i -= 1;
        } else {
            s2_iter.next();
            j -= 1;
        }
    }

    res
}

#[allow(dead_code)]
#[allow(clippy::needless_range_loop)]
fn print_mat<T: Debug>(mat: &[Vec<T>]) {
    for j in 0..mat[0].len() {
        for i in 0..mat.len() {
            print!("{:?} ", mat[i][j])
        }
        println!()
    }

    println!();
}

#[cfg(test)]
mod test {

    use crate::{lcs, lcs_len, test_format::TestFormat};

    #[test]
    fn run_tests() {
        for e in std::fs::read_dir("tests").expect("no test dir") {
            let entry = e.expect("err in entry");
            let path = entry.path();

            println!("testing {}", path.display());

            let test = TestFormat::parse(path);

            let res = lcs(&test.s1, &test.s2);
            assert!(test.result == res);

            let res = lcs_len(&test.s1, &test.s2);
            assert!(test.result_size == res);
        }
    }

    #[test]
    fn run_test() {
        let test = TestFormat::parse("tests/adn-10-10.test");

        let res = lcs(&test.s1, &test.s2);
        assert!(test.result == res);

        let res = lcs_len(&test.s1, &test.s2);
        assert!(test.result_size == res);
    }
}