DPcontest E (LCS)

atcoder.jp

LCS(Longest Common Subsequence)最長経路問題です。

問題

文字列s , tが与えられた時に共通部分列で最長の物を求める.

最初全探索するのかと思ったが明らかに実行時間が間に合わない。それならばDPだろう.今回のDPの定義としては

   lcs[i][j] : 文字列sのi文字目まで,文字列tのj文字目まで見た時の最長の部分列の長さ

例

s = "aabbccd"
t = "abcabcd"
この場合答えは"abcd"になります。このlcsを求める問題では最長の部分列の長さが同じ複数回答生じる場合もあります。
DPで重要な初期値と漸化式(推移条件)を見ていきます.

   lcs[0][j] = 0;  { j = 0,1,2, ... }
   lcs[i][0] = 0;  { i = 0,1,2, ... }

このようになります.片方の文字列の長さが0の時には共通する文字列は存在しないので長さが0になります.
次に漸化式を見ていくのですがこれが曲者でした.

{ 文字列sのi番目  == 文字列tのj番目 }
    lcs[i][j] = lcs[i - 1][j - 1] + 1 ;

{ 文字列sのi番目 != 文字列tのj番目 }
    lcs[i][j] = max( lcs[i - 1][j] , lcs[i][j - 1]) ;

この漸化式はlcs[i][j] を知りたければ

    lcs[i - 1][j - 1]
    lcs[i - 1][j]
    lcs[i][j - 1]

の3つがわかっていることで lcs[i][j] を確実に求められるということです.DPを解く時には前の結果がわかっている必要があるという規則に乗っ取っています.

漸化式を紐解く

漸化式の一つ目lcs[i][j] = lcs[i - 1][j - 1] + 1 ;というのは二つの文字列に共通の文字を加えることにより長さを一つ大きくできることを示しています.
次に二つめの漸化式.追加する文字が違う時に使います.追加する文字が違う場合はそれまでの文字列に相手の追加された文字が含んでいるかを確認しなければならないのですがそれは既に終わっているので大きい方を取り込めば成立します。