最長共通部分列 (Longest Common Subsequence ,LCS)

概要

以下のような問題

  • 長さ \(N\) の文字列 \(S\) と長さ \(M\) の文字列 \(T\) がある

  • 文字列 \(S\) と文字列 \(T\) の共通部分列の中で、最長となる長さ、もしくは部分文字列を求めよ

以下のようなDPを考える。

  • \(dp[i][j] :=\) \(S\) のi文字目、 \(T\) のj文字目からの最長部分文字列の長さ

復元は \(i = j = 0\) から始め、

  • \(S_i = T_j\) の時は解にその文字を追加し、 \(i \leftarrow i + 1\), \(j \leftarrow j + 1\) に遷移

  • それ以外は \(dp[i+1][j]\), \(dp[i][j+1]\) の内、 \(dp[i][j]\) と等しくなる方の遷移

という感じで処理すればよい

計算量

\(O(NM)\)

実装

def solve(S, T):
    L1 = len(S)
    L2 = len(T)
    dp = [[0]*(L2+1) for i in range(L1+1)]

    for i in range(L1-1, -1, -1):
        for j in range(L2-1, -1, -1):
            r = max(dp[i+1][j], dp[i][j+1])
            if S[i] == T[j]:
                r = max(r, dp[i+1][j+1] + 1)
            dp[i][j] = r

    # dp[0][0] が長さの解

    # ここからは復元処理
    res = []
    i = 0; j = 0
    while i < L1 and j < L2:
        if S[i] == T[j]:
            res.append(S[i])
            i += 1; j += 1
        elif dp[i][j] == dp[i+1][j]:
            i += 1
        elif dp[i][j] == dp[i][j+1]:
            j += 1
    return "".join(res)

Verified

  • AtCoder: "Educational DP Contest - F問題: LCS": source (PyPy3, 458ms)

戻る