Struct LCS

pub struct LCS<'a, T> {
    pub A: &'a [T],
    pub B: &'a [T],
    pub N: usize,
    pub M: usize,
    pub lcs: usize,
    pub dp: Vec<Vec<usize>>,
}

最長共通部分列

Fields

A: &'a [T]

B: &'a [T]

N: usize

M: usize

lcs: usize

dp: Vec<Vec<usize>>

Implementations

impl<'a, T: PartialEq> LCS<'a, T>

pub fn build(A: &'a [T], B: &'a [T]) -> Self

動的計画法により最長共通部分列の長さを求める

• 時間計算量: $O(NM)$

pub fn reconstruct(&self) -> Vec<&T>

最長共通部分列を復元する

• 時間計算量: $O(N + M)$