LCSの解き方【競技プログラミング】

はじめに

• LCS(longest common subsequence)の解法はド定番らしく、逆に丁寧に説明されてないことが多いので、最初、よく分からなかったから、自分で備忘的にまとめることにした。

LCSとは？

• 文字列SとTの部分文字列の集合のうち、一致する部分文字列の中で最長の長さのものを答えよ、と言うもの。
  • 文字列Sの部分文字列の集合とは、例えば、S="abc"のとき、["abc","ab","ac","bc","a","b","c",""]の8つの文字列となる。
  • つまり、長さNの文字列の時、各文字に対し、残す/残さないの2択が可能なので、$2^N$個の部分文字列を作れる。
• 例えば、S="abcdef"、T="cdabe"であれば、LCSの長さは3となり、LCSは"abe"と"cde"になる。
• 例題としては、DPまとめコンテストのf問題がある。

簡単に説明される場合の解法

• dp[i][j]を「文字列Sの文字0..<i」「文字列Tの文字0..<j」によるLCSとする。

extension Array {
    init(_ cnt: Int, _ v: Element) {
        self = [Element](repeating: v, count: cnt)
    }
    init<T>(_ cnt2:Int, _ cnt1:Int, _ v:T) where Element == [T] {
        self = [[T]](cnt2,[T](cnt1,v))
    }
}

// 準備
var dp = [[Int]](S.count+1,T.count+1,O) // 上記extensionによる省略書式

// 遷移
for i in 0..<S.count {
    for j in 0..<T.count {
        dp[i+1][j+1] = max( // ①
            S[i] == T[j] ? dp[i][j] + 1 : 0 // ②
            dp[i+1][j], // ③
            dp[i][j+1], // ④
  
        )
    }
}

// 答え
print(dp[S.count][T.count])

• 上記を見て、一般的なdpと違うのは、①において、遷移後のインデックスが「i+1」だけでなく「j+1」もあるってこと。違和感を感じない人は、まぁ良いけどね。この時点で、「j+1」があること自体は、まぁ問題はない。
• 次に、②を見ると、「あぁ、文字が一致するときは、dpを1足すのね。納得」となり、何の問題はない。
• で、違和感バリバリなのが、③④で、遷移前の状態を表す側のインデックスに「i+1」「j+1」が存在すること。
  • ちょ、待てよ！遷移前に「i+1」「j+1」の情報を保持してるってあり得るの？
  • でも、このコードで例題を問題なく解けてんだよなぁ。でも、納得いかんなぁ。
• で、結局③④について納得感を得るために、コードに確認用のprint文を追加して、中身を若干修正して回してみた。結果が長くなるのは嫌だから、S="abc"、T="zbz"として、LCS="b"（長さ1）となるようにした。

var dp = [[Int]](S.count+1,T.count+1,8) // 初期値を8とした。なんとなく、縁起が良いから？

// 真の初期値を設定。SかTのどちらかで、1文字もチェックしてなければ、LCSの長さは0になる。
for i in 0...S.count { dp[i][0] = 0 }
for j in 0...T.count { dp[0][j] = 0 }

for i in 0..<S.count {
    for j in 0..<T.count {

        //遷移処理前のdpを表示
        print("処理前：",i,j)
        dp.forEach{
            print($0)
        }    
        
        dp[i+1][j+1] = max( // ①
            S[i] == T[j] ? dp[i][j] + 1 : -1 // ② -- 説明のわかりやすさのため、falseのときは-1にして、max関数で選ばれないようにした。
            dp[i+1][j], // ③
            dp[i][j+1], // ④
        )

        //遷移処理後のdpを表示
        print("処理後：",i,j)
        dp.forEach{
            print($0)
        }  
        
        print() // 見やすさのための改行
        
    }
}

• 上記コードを回した結果は以下のとおり。なお、下記の（）内の数値は、dpが上記コードで遷移するインデックス[i+1][j+1]①を指し、丸数値は、上記コードmax関数で採用される値(②③④のどれか)を指す。

処理前： 0 0
[0, 0, 0, 0]
[0, 8, 8, 8]
[0, 8, 8, 8]
[0, 8, 8, 8]
処理後： 0 0
[0, 0, 0, 0]
[0, 0, 8, 8] // 8→0 （1，1）③④
[0, 8, 8, 8]
[0, 8, 8, 8]

処理前： 0 1
[0, 0, 0, 0]
[0, 0, 8, 8]
[0, 8, 8, 8]
[0, 8, 8, 8]
処理後： 0 1
[0, 0, 0, 0]
[0, 0, 0, 8] // 8→0（1，2）③④
[0, 8, 8, 8]
[0, 8, 8, 8]

処理前： 0 2
[0, 0, 0, 0]
[0, 0, 0, 8]
[0, 8, 8, 8]
[0, 8, 8, 8]
処理後： 0 2
[0, 0, 0, 0]
[0, 0, 0, 0] // 8→0（1，3）③④
[0, 8, 8, 8]
[0, 8, 8, 8]

処理前： 1 0
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 8, 8, 8]
[0, 8, 8, 8]
処理後： 1 0
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 8, 8] // 8→0（2，1）③④
[0, 8, 8, 8]

処理前： 1 1
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 8, 8]
[0, 8, 8, 8]
処理後： 1 1
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 1, 8] // 8→1（2，2）②
[0, 8, 8, 8]

処理前： 1 2
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 1, 8]
[0, 8, 8, 8]
処理後： 1 2
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 1, 1] // 8→1（2，3）③
[0, 8, 8, 8]

処理前： 2 0
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 1, 1]
[0, 8, 8, 8]
処理後： 2 0
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 1, 1]
[0, 0, 8, 8] // 8→0（3，1）③④

処理前： 2 1
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 1, 1]
[0, 0, 8, 8]
処理後： 2 1
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 1, 1]
[0, 0, 1, 8] // 8→1（3，2）④

処理前： 2 2
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 1, 1]
[0, 0, 1, 8]
処理後： 2 2
[0, 0, 0, 0]
[0, 0, 0, 0]
[0, 0, 1, 1]
[0, 0, 1, 1] // 8→1（3，3）③④

• こうやって回してみると、真の初期値設定for i in 0...S.count { dp[i][0] = 0 }とfor j in 0...T.count { dp[0][j] = 0 }が効いていることが分かるね。
• この初期値設定が、上記dpのマス目において、上辺と左辺の0を形成し、それが「右③」、「下④」または「右下②（1加算）」に遷移しているから、仮初期値の「8」が全て置き換わった。
• なお、二重forループiとjを逆にしても、「処理後:2 2」のdpは同じになる。
• うむ、頭の回転の衰えてきた僕でも納得した！

続き（LCSの文字列の取得）-- 計算量無視版

• 上記までだと、LCSの文字数しか出せなかったね。まぁ、文字列を取得するロジックは簡単で、ちょっと書き換えれば出来上がり。
• 具体的には、dp配列が「文字数」を格納していたところ、「文字」を格納することとなる。
• dpの中身が文字となったことから、元のコードのmax関数で②③④で最長のものを選ぶ部分が、少し面倒くさい。

var dp = [[String]](S.count+1,T.count+1,"")

for i in 0..<S.count {
    for j in 0..<T.count {

        var longest = dp[i+1][j].count // 元の③に相当
        dp[i+1][j+1] = dp[i+1][j]
        
        if dp[i][j+1].count > longest { // 元の④に相当
            longest = dp[i][j+1].count
            dp[i+1][j+1] = dp[i][j+1]
            
        }
        
        if (S[i] == T[j] ? dp[i][j].count + 1 : 0) > longest { // 元の②に相当
            dp[i+1][j+1] = dp[i][j] + String(S[i])
        }

    }
}

print(dp[S.count][T.count])

• 例題の下記入力を与えて回すと...

abracadabra // S
avadakedavra // T

• 答え（aaadara）と一致したからOK！...って思うじゃん？提出するとTLEなのよね。
• 制約って、S、Tとも3000文字以下。だから、二重forループを回すだけなら$10^7$以下になるはずなんだよね。
• でも、forループの一番内側で行っているのは、文字列操作なんだよね。
• 例えば、dp[i+1][j+1] = dp[i+1][j]について言えば、右辺の内容を左辺に上書きしている。この上書きしている内容が整数等であれば大した話ではないが、内容が「文字列」だとすると、その実態は配列だから、配列のコピー作業と考えると、O(文字数)の計算量がかかると言うことだろうか。そう考えると、計算量は$|S|^3$に跳ね上がるから、$9×10^9$になるから、TLEになってもおかしくないね。

続き（LCSの文字列の取得）-- 計算量考慮版

• 初心に返って、LCSの文字列の長さは、当初の手法で求めることとする。

// 準備
var dp = [[Int]](S.count+1,T.count+1,O) // 上記extensionによる省略書式

// 遷移
for i in 0..<S.count {
    for j in 0..<T.count {
        dp[i+1][j+1] = max( // ①
            S[i] == T[j] ? dp[i][j] + 1 : 0 // ②
            dp[i+1][j], // ③
            dp[i][j+1], // ④
  
        )
    }
}

// 答え
print(dp[S.count][T.count])

• さて、ここで得た、配列dpを元に、文字を取りだしてみる。
• 答えから書いちゃうと以下のとおり

var ans = ""

var i = S.count
var j = T.count

while i * j > 0 {
    // (i-1, j) -> (i, j) と更新されていた場合
    if (dp[i][j] == dp[i-1][j]) { i -= 1 }

    // (i, j-1) -> (i, j) と更新されていた場合
    else if (dp[i][j] == dp[i][j-1]) { j -= 1 }

    // (i-1, j-1) -> (i, j) と更新されていた場合
    else {
        ans = String(S[i-1]) + ans // 文字を復元する
        i -= 1 ; j -= 1
    }
}
print(ans)

• まぁ、説明しなくても、分かるかな？

さいごに

• Stringの計算量のせいで、LCSの長さパートと文字列復元パートの2つに別れるのが面倒だね。
• でもまぁ、これは一度覚えれば何とかなるタイプ！
• めでたしめでたし