F - LCS（動的計画法⑨）

問題

文字列 a および ｂ が与えられます。

a の部分列かつ ｂ の部分列であるような文字列のうち、最長のものをひとつ求めてください。

【注釈】

文字列 x の 部分列 とは、x から 0 個以上の文字を取り除いた後、

残りの文字を元の順序で連結して得られる文字列のことです。

解法・ソースコード

最長共通部分列 の長さを求める問題は以前の記事で解いています。

最長共通部分列（動的計画法③）- https://ailogsite.netlify.app/2022/12/16/2022/1216/

今回は、さらに「最長共通部分列を具体的にどれか1つ」求める方法を考えます。

基本的な考え方としては メモ化テーブルの 終端ノード memo[(len(a), len(b)] から順に どのノードから更新されて来たのか、その元となる部分を辿って行く ことになります。

メモ化テーブルの値を見ながら、今いる ノード (i, j) がどのノードから更新されて来たのかを特定し、求める 最長共通部分の文字列 を復元していきます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#---------- 入力例1 ----------
a = 'axyb'
b = 'abyxb'
#---------- 入力例2 ----------
# a = 'aa'
# b = 'xayaz'
#---------- 入力例3 ----------
# a = 'a'
# b = 'z'
#---------- 入力例4 ----------
# a = 'abracadabra'
# b = 'avadakedavra'
#-----------------------------
# メモ化テーブル
memo = {}
x = ''
for i, a1 in enumerate(a):
    for j, b1 in enumerate(b):
        # print(i,j,a1,b1)
        if a1 == b1:
            # print('  #', a1,i,j)
            memo[i + 1, j + 1] = memo.get((i, j), 0) + 1
        else:
            memo[i + 1, j + 1] = max(memo.get((i, j + 1), 0), memo.get((i + 1, j), 0))
print('長さ：', memo[(len(a), len(b))])

# メモ化テーブルの値を見ながら、今いるノード (i,j)(i,j) がどのノードから更新されて来たのかを特定する
i, j = len(a), len(b)

res = ''    # 求める最長の文字列   
while i > 0 and j > 0:
    if memo.get((i, j), 0) == memo.get((i - 1, j), 0):    # (i-1, j) -> (i, j) と更新されていた場合
        i -= 1
    elif memo.get((i, j), 0) == memo.get((i, j - 1), 0):  # (i, j-1) -> (i, j) と更新されていた場合
        j -= 1
    else:                           # (i-1, j-1) -> (i, j) と更新されていた場合
        res = a[i - 1] + res        # 求める文字列を復元する　a[j - 1]でも可
        i -= 1
        j -= 1
print('解：', res)

[実行結果(入力例1)]

長さ： 3
解： axb

答えは axb または ayb です。 どちらを出力しても正解です。

[実行結果(入力例2)]

長さ： 2
解： aa

答えは aa となります。

[実行結果(入力例3)]

長さ： 0   
解：

答えは (空文字列) です。

[実行結果(入力例4)]

長さ： 7
解： aaadara

答えは aaadara となります。