haar_lib/algo/
lcs.rs

1//! 最長共通部分列
2
3use crate::chmax;
4
5/// 列a, bの最長共通部分列の一つを求める。
6///
7/// **Time complexity** $O(|a||b|)$
8pub fn lcs<T: Copy + PartialEq>(a: &[T], b: &[T]) -> Vec<T> {
9    let n = a.len();
10    let m = b.len();
11
12    let mut dp = vec![vec![0; m + 1]; n + 1];
13
14    for i in 1..=n {
15        for j in 1..=m {
16            if a[i - 1] == b[j - 1] {
17                chmax!(dp[i][j], dp[i - 1][j - 1] + 1);
18            } else {
19                chmax!(dp[i][j], dp[i - 1][j]);
20                chmax!(dp[i][j], dp[i][j - 1]);
21            }
22        }
23    }
24
25    let mut ret = Vec::with_capacity(dp[n][m]);
26    lcs_restore(&dp, a, b, n, m, &mut ret);
27
28    ret
29}
30
31fn lcs_restore<T: Copy + PartialEq>(
32    dp: &[Vec<usize>],
33    a: &[T],
34    b: &[T],
35    i: usize,
36    j: usize,
37    ret: &mut Vec<T>,
38) {
39    if i == 0 || j == 0 {
40        return;
41    }
42    if a[i - 1] == b[j - 1] {
43        lcs_restore(dp, a, b, i - 1, j - 1, ret);
44        ret.push(a[i - 1]);
45    } else if dp[i - 1][j] >= dp[i][j - 1] {
46        lcs_restore(dp, a, b, i - 1, j, ret);
47    } else {
48        lcs_restore(dp, a, b, i, j - 1, ret);
49    }
50}
haar_lib/algo/lcs.rs

haar_lib/algo/
lcs.rs
