def lcs(s1, s2): m, n = len(s1), len(s2) dp = [[0] * (n+1) for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) res = "" i, j = m, n while i > 0 and j > 0: if s1[i-1] == s2[j-1]: res = s1[i-1] + res i -= 1 j -= 1 elif dp[i-1][j] > dp[i][j-1]: i -= 1 else: j -= 1 return res, dp[m][n]运行不出来

这段代码如果运行不出来，很可能是因为缺少函数调用。你需要在代码的下面添加调用函数的语句，例如：

s1 = "ABCD"
s2 = "EACB"
print(lcs(s1, s2)) # 输出：('AC', 2)

这里将两个字符串s1和s2作为参数传递给lcs函数，并将结果打印输出。你可以根据自己的需要修改这些参数。

相关问题

设计最长公共子序列问题的动态规划算法 要求： 随机生成一个一万个字符的字符串s1的数据文件Character.txt。发出k（k=100）个随机数整数[0,9999]下标，给这k个字符随机赋值，形成第二个一万个字符的字符串s2。求这两个字符串的LCS，并计算重复率=Length(LCS)/Length(s1)。

最长公共子序列问题可以使用动态规划算法求解。具体算法步骤如下：

1. 定义状态：令dp[i][j]表示s1前i个字符和s2前j个字符的LCS长度。

2. 初始化状态：dp[0][j]和dp[i][0]均为0，其中0<=i<=len(s1), 0<=j<=len(s2)。

3. 状态转移：若s1[i]==s2[j]，则dp[i][j]=dp[i-1][j-1]+1；否则dp[i][j]=max(dp[i-1][j],dp[i][j-1])。

4. 最终结果：dp[len(s1)][len(s2)]即为s1和s2的LCS长度。

代码实现如下：

def LCS(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

# 读取数据
with open('Character.txt', 'r', encoding='utf-8') as f:
    s1 = f.read()

# 生成随机数
import random
k = 100
indices = random.sample(range(len(s1)), k)

# 修改s1中的字符
s2 = list(s1)
for idx in indices:
    s2[idx] = chr(random.randint(0, 127))
s2 = ''.join(s2)

# 计算LCS和重复率
lcs_len = LCS(s1, s2)
repeat_rate = lcs_len / len(s1)
print('LCS长度为：', lcs_len)
print('重复率为：', repeat_rate)

需要注意的是，在实现中，为了方便，将字符用ASCII码表示，因此可能存在一些不可见字符。如果需要可视化输出LCS，可以将LCS的长度和最长公共子序列本身一并返回。

python实现lcs算法

LCS（最长公共子序列）算法是一种常见的字符串匹配算法，可以用来求解两个字符串的最长公共子序列。下面是 Python 实现的 LCS 算法代码：

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

其中，`s1` 和 `s2` 分别是两个字符串，`m` 和 `n` 分别是它们的长度。`dp` 是一个二维数组，用来存储最长公共子序列的长度。

算法的核心是一个二重循环，它遍历 `s1` 和 `s2` 的所有字符，并根据字符是否相等更新 `dp` 数组的值。最终，`dp[m][n]` 就是两个字符串的最长公共子序列的长度。

如果需要输出最长公共子序列，可以使用回溯法，代码如下：

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    i, j = m, n
    res = []
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            res.append(s1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return ''.join(res[::-1])

这里使用了 `res` 列表来存储最长公共子序列中的字符，最后再将其反转并转化为字符串输出。