最长公共子序列
"""
LCS Problem Statement: Given two sequences, find the length of longest subsequence
present in both of them. A subsequence is a sequence that appears in the same relative
order, but not necessarily continuous.
Example:"abc", "abg" are subsequences of "abcdefgh".
"""
def longest_common_subsequence(x: str, y: str):
"""
Finds the longest common subsequence between two strings. Also returns the
The subsequence found
Parameters
----------
x: str, one of the strings
y: str, the other string
Returns
-------
L[m][n]: int, the length of the longest subsequence. Also equal to len(seq)
Seq: str, the subsequence found
>>> longest_common_subsequence("programming", "gaming")
(6, 'gaming')
>>> longest_common_subsequence("physics", "smartphone")
(2, 'ph')
>>> longest_common_subsequence("computer", "food")
(1, 'o')
"""
# find the length of strings
assert x is not None
assert y is not None
m = len(x)
n = len(y)
# declaring the array for storing the dp values
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
match = 1 if x[i - 1] == y[j - 1] else 0
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] + match)
seq = ""
i, j = m, n
while i > 0 and j > 0:
match = 1 if x[i - 1] == y[j - 1] else 0
if dp[i][j] == dp[i - 1][j - 1] + match:
if match == 1:
seq = x[i - 1] + seq
i -= 1
j -= 1
elif dp[i][j] == dp[i - 1][j]:
i -= 1
else:
j -= 1
return dp[m][n], seq
if __name__ == "__main__":
a = "AGGTAB"
b = "GXTXAYB"
expected_ln = 4
expected_subseq = "GTAB"
ln, subseq = longest_common_subsequence(a, b)
print("len =", ln, ", sub-sequence =", subseq)
import doctest
doctest.testmod()
关于此算法
问题陈述
给定两个字符串S和T，找到最长公共子序列 (LCS) 的长度。
方法
令dp[i][j]为前缀S[1..i]和T[1..j]的最长公共子序列的长度。我们的答案（LCS 的长度）是dp[|S|][|T|]，因为字符串长度的前缀就是字符串本身。
对于任何i，dp[0][i]和dp[i][0]都为0，因为空前缀与任何其他字符串的 LCS 都是空字符串。
现在让我们尝试计算任何i、j的dp[i][j]。假设S[1..i] = *A且T[1..j] = *B，其中*代表任何字母序列（对于S和T可以不同），A代表任何字母，B代表任何与A不同的字母。由于A != B，我们的 LCS 不包含A或B作为最后一个字符。因此，我们可以尝试丢弃A或B字符。如果我们丢弃A，我们的 LCS 长度将为dp[i - 1][j]（因为我们有前缀S[1..i - 1]和T[1..j]）。如果我们尝试丢弃B字符，我们将拥有前缀S[1..i]和T[1..j - 1]，因此 LCS 的长度将为dp[i][j - 1]。由于我们正在寻找最长公共子序列，因此我们将从dp[i][j - 1]和dp[i - 1][j]中选择最大值。
但是如果S[1..i] = *A且T[1..j] = *A呢？我们可以说我们的前缀的 LCS 是前缀S[1..i - 1]和T[1..j - 1]的 LCS 加上字母A。因此，如果S[i] = T[j]，则dp[i][j] = dp[i - 1][j - 1] + 1。
我们可以看到，我们可以逐行逐列地填充我们的dp表。因此，我们的算法将如下所示：
- 假设我们有两个字符串
S，长度为 N，T，长度为 M（从 1 开始编号）。让我们创建一个大小为(N + 1) x (M + 1)的表dp，从 0 开始编号。 - 让我们用 0 填充
dp的第 0 行和第 0 列。 - 然后，我们遵循以下算法：
for i in range(1..N):
for j in range(1..M):
if(S[i] == T[j])
dp[i][j] = dp[i - 1][j - 1] + 1
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
时间复杂度
O(N * M)在任何情况下
空间复杂度
O(N * M) - 简单实现 O(min {N, M}) - 两层实现（因为dp[i][j]仅依赖于第 i 层和第 i 层，我们可以只存储两层）。
示例
假设我们有字符串ABCB和BBCB。我们将构建这样的表格：
# # A B C B
# 0 0 0 0 0
B 0 ? ? ? ?
B 0 ? ? ? ?
C 0 ? ? ? ?
B 0 ? ? ? ?
现在我们将从第 1 行开始填充我们的表格。由于S[1] = A且T[1] = B，因此dp[1][1]将是dp[0][1] = 0和dp[1][0] = 0的最大值。所以dp[1][1] = 0。但是现在S[2] = B = T[1]，所以dp[1][2] = dp[0][1] + 1 = 1。dp[1][3]是1，因为A != C，我们选择max{dp[1][2], dp[0][3]}。而dp[1][4] = dp[0][3] + 1 = 1。
# # A B C B
# 0 0 0 0 0
B 0 0 1 1 1
B 0 ? ? ? ?
C 0 ? ? ? ?
B 0 ? ? ? ?
现在让我们填充表格的其他部分：
# # A B C B
# 0 0 0 0 0
B 0 0 1 1 1
B 0 0 1 1 2
C 0 0 1 2 2
B 0 0 1 2 3
因此，LCS 的长度是dp[4][4] = 3。
