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=hellohelen2023，s2=helenhello2048，那么两个串的最长公共子串长度为

为了找到两个字符串`s1`和`s2`的最长公共子串，我们可以使用动态规划的方法。这里我们寻找的是连续子串的最长公共部分，而不是最长公共子序列（ LCS），因为题目要求子串必须是连续的。

首先，让我们定义一个二维数组`dp`，其中`dp[i][j]`表示从`s1`的第一个字符到第`i`个字符和`s2`的第一个字符到第`j`个字符之间的最长连续公共子串的长度。然后我们遍历两个字符串，更新`dp`数组：

def longest_common_substring(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    
    max_length = 0
    end_index = 0

    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
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    end_index = i - 1
    
    return s1[end_index-max_length+1:end_index+1], max_length

s1 = "hellohelen2023"
s2 = "helenhello2048"

substring, length = longest_common_substring(s1, s2)
print(f"最长公共子串是'{substring}'，长度为{length}")

在这个例子中，`substring`变量会存储最长公共子串，`length`变量则是其长度。运行这段代码，你会得到结果。

设计最长公共子序列问题的动态规划算法 要求： 随机生成一个一万个字符的字符串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的长度和最长公共子序列本身一并返回。