cp_library_rs/string/
lcs.rs

1//! ## 最長共通部分列
2
3use crate::chmax;
4
5/// 最長共通部分列
6pub struct LCS<'a, T> {
7    pub A: &'a [T],
8    pub B: &'a [T],
9    pub N: usize,
10    pub M: usize,
11    pub lcs: usize,
12    pub dp: Vec<Vec<usize>>,
13}
14
15impl<'a, T: PartialEq> LCS<'a, T> {
16    /// 動的計画法により最長共通部分列の長さを求める
17    /// - 時間計算量: $`O(NM)`$
18    pub fn build(A: &'a [T], B: &'a [T]) -> Self {
19        let (N, M) = (A.len(), B.len());
20        let mut dp = vec![vec![0; M + 1]; N + 1];
21
22        for (i, a) in A.iter().enumerate() {
23            for (j, b) in B.iter().enumerate() {
24                if a == b {
25                    chmax!(dp[i + 1][j + 1], dp[i][j] + 1);
26                }
27                chmax!(dp[i + 1][j + 1], dp[i + 1][j]);
28                chmax!(dp[i + 1][j + 1], dp[i][j + 1]);
29            }
30        }
31
32        Self {
33            A,
34            B,
35            N,
36            M,
37            lcs: dp[N][M],
38            dp,
39        }
40    }
41
42    /// 最長共通部分列を復元する
43    /// - 時間計算量:  $`O(N + M)`$
44    pub fn reconstruct(&self) -> Vec<&T> {
45        let mut res = vec![];
46        let mut i = self.N;
47        let mut j = self.M;
48
49        while i > 0 && j > 0 {
50            if self.A[i - 1] == self.B[j - 1] {
51                res.push(&self.A[i - 1]);
52                i -= 1;
53                j -= 1;
54            } else if self.dp[i - 1][j] > self.dp[i][j - 1] {
55                i -= 1;
56            } else {
57                j -= 1;
58            }
59        }
60
61        res.reverse();
62        res
63    }
64}
cp_library_rs/string/lcs.rs

cp_library_rs/string/
lcs.rs
