アルゴリズム学習-LCS最長共通サブシーケンス

アルゴリズム学習-LCS最長共通サブシーケンス
0 x 01概要
LCS全称Longest Common Subsequence、すなわち最長共通サブシーケンス問題.本明細書の実装コードはPythonを用いる.
0 x 02考え方
まず再帰的な方法で考えるのが簡単ですが、欠点は繰り返し計算があり、性能が低いことです.
この問題は親問題と子問題の関係であり,動的計画アルゴリズムの採用が考えられる.
記状態遷移2次元配列dp[i][j]は、文字列aから0からi-1、文字列bから0からj-1の最長共通サブシーケンスを表す.
導出された状態遷移方程式は以下の通りである.

#  a[i-1] == b[j-1] 
dp[i][j] = dp[i-1][j-1] + a[i-1]

#  len(dp[i-1][j]) > len(dp[i][j-1])
dp[i][j] = dp[i-1][j]

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

1からlen+1までa,b文字列を遍歴し、最終的に得られるdp[len_a][len_b]は、文字列aと文字列bの最長共通サブシーケンスを表す最終結果である.
0 x 03ダイナミックプランニング実装コード
python実装コードは次のとおりです.

# -*- coding:utf-8 -*-

#                
def lcs_dynamic_planning(a, b):
    len_a = len(a)
    len_b = len(b)
    #         ，            ，   len+1
    dp = [['' for i in range(len_b+1)] for j in range(len_a+1)]

    for i in range(1, len_a + 1):
        for j in range(1, len_b + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + a[i-1]
            else:
                lcs_1 = dp[i-1][j]
                lcs_2 = dp[i][j-1]
                if len(lcs_1) > len(lcs_2):
                    dp[i][j] = lcs_1
                else:
                    dp[i][j] = lcs_2
    return dp[len_a][len_b]

print(lcs_dynamic_planning('hello world', 'hero word'))

結果は次のとおりです.

heo word