この記事でやること
前回の記事で、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を使って計算することができる