概要 [1] で紹介されている LCS のワードサイズ高速化について、自分の理解を記します。 特に新しい主張はないです。 内容は [2] を大きく参考にしています。 dp 配列とその差分 を二つの文字列 の LCS の長さ、と定義します。 次が成り立ちます。 \begin{align*} \mathrm{dp}_{i, j} = \begin{cases} 0 & (i = 0 \ \mathrm{or}\ j = 0) \\ \mathrm{dp}_{i-1, j-1} + 1 & (S_i = T_j) \\ \max( \mathrm{dp}_{i-1, j}, \mathrm{dp}_…