【解説】　最長共通部分列問題(LCS)

入力例 4

abracadabra
avadakedavra

出力例 4

ただし、このたどり方にはルールがあります。下の図のように隣接する数字がすべて同じ場合は、斜め上に移動します。

次に、縦方向や横方向に移動する場合は数字が高いものを通るように移動します。なお、縦方向は文字列sに存在しない文字、横方向は文字列tに存在しない文字の場合。

この問題では、漸化式を使用して考えます。

1. 漸化式の定義

2つの文字列を s（長さ n）、t（長さ m）とします。

dp[i][j] を「s の i 文字目までと t の j 文字目までにおけるLCSの長さ」と定義します。

ご指摘の通り、漸化式は以下のようになります。

1. s[i] == t[j] のとき（文字が一致する場合）

   その文字をLCSに含めることができるため、1つ前の状態に +1 します。

   dp[i][j] = dp[i-1][j-1] + 1

2. s[i] \neq t[j] のとき（文字が一致しない場合）

   s を1文字削った場合と、tを1文字削った場合の、値が大きい方を引き継ぎます。

   dp[i][j] = max(dp[i-1][j], dp[i][j-1])

2. 文字列の復元方法

DPテーブルが完成すると、dp[n][m] にLCSの最大長が格納されます。ここから具体的な文字列を特定するには、テーブルをゴール（右下）からスタート（左上）へ逆順に辿ります。

• s[i] == t[j] ならば：

  その文字はLCSに含まれる文字です。結果の先頭に追加し、斜め上 (i-1, j-1) へ移動します。

• dp[i][j] == dp[i-1][j] ならば：

  s の i 文字目を使わなくても現在の長さが維持できているため、上 (i-1) へ移動します。

• それ以外 (dp[i][j] == dp[i][j-1]) ならば：

  左 (j-1) へ移動します。

（参考）この漸化式を踏まえたPythonコードは次のようです。一つしか出力できませんが、コードは読みやすいと思います。

# LCSのひとつを表示する

def solve_lcs(s, t):

    n = len(s)

    m = len(t)

   

    # DPテーブルの初期化 (n+1) x (m+1)

    # dp[i][j] は sのi文字目までと tのj文字目までのLCSの長さ

    dp = [[0] * (m + 1) for _ in range(n + 1)]

   

    # 1. DPテーブルを埋める

    for i in range:

        for j in range(m):

            if s[i] == t[j]:

                dp[i+1][j+1] = dp[i][j] + 1

            else:

                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])

   

    # 2. 文字列の復元 (後ろから辿る)

    res = []

    i, j = n, m

    while i > 0 and j > 0:

        if s[i-1] == t[j-1]:

            # 文字が一致する場合、その文字を採用して斜め上へ

            res.append(s[i-1])

            i -= 1

            j -= 1

        elif dp[i][j] == dp[i-1][j]:

            # 上のセルと同じ値なら、上へ移動

            i -= 1

        else:

            # 左のセルと同じ値なら、左へ移動

            j -= 1

           

    # 逆順で格納されているので反転させる

    return "".join(reversed(res))

# テスト実行

s = "abcbdab"

t = "bdcaba"

result = solve_lcs(s, t)

print(f"文字列1: {s}")

print(f"文字列2: {t}")

print(f"LCS: {result}")

print(f"長さ: {len(result)}")