EDPC F - LCS

考え方

ABCでいうと、E問題級。

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

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

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

入力例1での動作

入力を受け取る。

s: axyb
t: abyxb

dp[i][j] を、s の先頭 $i$ 文字と t の先頭 $j$ 文字での最長共通部分列の長さとする。

DP テーブルを埋めると、次のようになる。

最後に、右下からバックトレースする。

まず、s[3] と t[4] はどちらも b なので、答えに b を追加する。
その後、s[2] と t[3] は異なるので、DP テーブルの値を保てる方へ戻る。

次に、s[1] と t[3] はどちらも x なので、答えに x を追加する。
その後、s[0] と t[2]、s[0] と t[1] は異なるので、DP テーブルの値を保てる方へ戻る。

最後に、s[0] と t[0] はどちらも a なので、答えに a を追加する。

この時点で、後ろから見た答えは bxa である。
これを反転した axb が答え。

注意点

特になし。

別解

特になし。