EDPC F - LCS

最長共通部分列

考え方

ABCでいうと、E問題級。

文字列 $S$ と $T$ の最長共通部分列を $1$ つ求める問題。

典型問題そのまま。
詳しくは「最長共通部分列」の記事参照。

計算量は $O(\lvert S\rvert\lvert T\rvert)$。

入力を受け取る。

s: axyb
t: abyxb

$S$ と $T$ の各接頭辞について考える。
各組の最長共通部分列の長さを求める。
表を埋めると次のようになる。

$S$ ＼ $T$	`a`	`ab`	`aby`	`abyx`	`abyxb`
空文字	0	0	0	0	0
`a`	1	1	1	1	1
`ax`	1	1	1	2	2
`axy`	1	1	2	2	2
`axyb`	1	2	2	2	3

右下から表を逆向きにたどり、実際の最長共通部分列を復元する。

まず、axyb と abyxb を見る。
末尾はどちらも b なので、b を採用する。
両方の末尾を取り除き、axy と abyx へ移る。

末尾の y と x は異なる。
axy の末尾を取り除いても、長さ $2$ を保てる。
そのため、ax と abyx の組へ移る。

この組では、末尾がどちらも x である。
x を採用して、両方の末尾を取り除く。
次は a と aby を見る。

末尾の a と y は異なる。
aby の末尾を取り除いても、長さ $1$ を保てる。
そのため、a と ab の組へ移る。
同様に、a と a の組まで移る。

最後は、末尾がどちらも a である。
a を採用する。

逆向きに採用した文字列は bxa となる。
これを反転した axb が答え。

特になし。

特になし。