この記事でやること

前回の記事で、2つの文字列の類似度を表すレーベンシュタイン距離とジャロ・ウィンクラー距離について説明した。

2つの文字列の一致度を表すものとして、他に最長共通部分列(Longest Common Subsequence: LCS)がある。
今回の記事はこのLCSの紹介をした後にPythonを使って実装してみる。

LCSとは？

定義は簡単で、単に二つの文字列の共通部分を表す。
この共通部分は必ずしも連続した文字である必要はなく、例えば"aa"と"xayaz"のLCSは"aa"となる。

この実装は競プロではお馴染みのdp (dynamic programming)で解けることが知られている。

解いてみる

AtCoderの過去の問題でちょうどいい問題があったのでPythonで解いてみる。

str1 = input()
str2 = input()
dp = [[0] * (len(str2)+1) for i in range(len(str1)+1)]

for i, vi in enumerate(str1):
    for j, vj in enumerate(str2):
        if vi == vj:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
#print(dp[len(str1)][len(str2)])

ans = []
i = len(str1) - 1
j = len(str2) - 1
while i >= 0 and j >= 0:
    if str1[i] == str2[j]:
        ans.append(str1[i])
        i -= 1
        j -= 1
    elif dp[i+1][j+1] == dp[i][j+1]:
        i -= 1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j -= 1
ans.reverse()
print(*ans, sep='')

最初のenumerateのloopでdpを計算し、それを用いて2回目のwhileのloopで共通する文字列を計算している。
単に"最大で何文字共通するか"だけを知りたければ最初のloopの後にdpを出力すれば求まる。

この値が大きいほど「共通部分が大きい = 2つも文字列が類似している」とイメージできそうだ。

まとめ

最長共通部分列 (LCS)について紹介した
LCSはdpを使って計算することができる