dsalgo 0.3.10

A package for Datastructures and 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
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

pub fn number_of_common_subsequences<T: Eq>(
    modulus: i64,
    a: &[T],
    b: &[T],
) -> i64 {
    let n = a.len();

    let m = b.len();

    let mut dp = vec![vec![1i64; m + 1]; n + 1];

    for i in 0..n {
        for j in 0..m {
            dp[i + 1][j + 1] = dp[i + 1][j] + dp[i][j + 1];

            if a[i] != b[j] {
                dp[i + 1][j + 1] -= dp[i][j];
            }

            dp[i + 1][j + 1] %= modulus;
        }
    }

    (dp[n][m] + modulus) % modulus
}

#[cfg(test)]

mod tests {

    use super::*;

    #[test]

    fn test() {
        let m = 1_000_000_007;

        let cases = vec![
            ((vec![1, 3], vec![3, 1]), 3),
            ((vec![1, 1], vec![1, 1]), 6),
            ((vec![3, 4, 5, 6], vec![3, 4, 5, 6]), 16),
            (
                (
                    vec![9, 6, 5, 7, 5, 9, 8, 5, 6, 7],
                    vec![8, 6, 8, 5, 5, 7, 9, 9, 7],
                ),
                191,
            ),
            (
                (
                    vec![
                        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                        1, 1,
                    ],
                    vec![
                        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
                        1, 1,
                    ],
                ),
                846527861,
            ),
        ];

        for ((a, b), ans) in cases {
            assert_eq!(number_of_common_subsequences(m, &a, &b), ans);
        }
    }
}