動的計画法による最長共通部分列

#Algorithm #String #Dynamic_Programming

Abstract

文字列$ S, Tの最長共通部分列 (Longest Common Subsequence) は動的計画法 (Dynamic Programming)を行って, バックトラックすることで求まる.

Explanation

TODO まだ.

Implementation

Input

文字列$ S, T

Output

文字列$ S, Tの最長共通部分列$ C

Time complexity

$ O(|S| |T|)time.

code:python

def longest_common_subseq(S, T):

if not S and not T: return ''

len_S, len_T = len(S), len(T)

dp = [0 * (len_T + 1) for i in range(len_S + 1)]

for i in range(len_S):

for j in range(len_T):

dpi+1j+1 = dpij + 1 if Si == Tj else max(dpi+1j, dpij+1)

# backtrack

C = ''

i, j = len_S, len_T

while i and j:

if Si-1 == Tj-1:

C += Si-1

i, j = i - 1, j - 1

else:

if dpij == dpi-1j: i -= 1

else: j -= 1

return C::-1

長さだけ欲しい場合は, 次のコードのほうが少し速い.

二つのリストを使いまわしている.

code:python

def longest_common_subseq(S, T):

if not S and not T: return 0

len_S, len_T = len(S), len(T)

dp = 0 * (len_T + 1)

prev = 0 * (len_T + 1)

for s in S:

for j in range(len_T):

if s == Tj: dpj+1 = prevj + 1

elif dpj > dpj+1: dpj+1 = dpj

prev = dp:

return dplen_T

Verification

最長共通部分列

References

最長増加部分列・最長共通部分列