用Python语言编写一个能计算最大公共子串长度的小程序,
时间: 2024-11-28 07:26:30 浏览: 10
在Python中,你可以通过动态规划的方法来编写一个计算两个字符串的最大公共子串长度的算法。这里是一个简单的例子,使用了二维数组记录每个位置上两个字符串的最长公共前缀:
```python
def longest_common_substring(s1, s2):
m = len(s1)
n = len(s2)
# 初始化一个二维数组,用于存储子问题的结果
dp = [[0] * (n + 1) for _ in range(m + 1)]
max_length = 0 # 最大公共子串长度
end_index = 0 # 当最大长度发生改变时,子串结束的位置
# 遍历矩阵,比较字符并更新dp值
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
else:
dp[i][j] = 0
# 使用end_index减去max_length得到最长公共子串的实际起始位置
start_index = end_index - max_length
return s1[start_index:end_index]
# 测试函数
s1 = "abcde"
s2 = "ace"
print(longest_common_substring(s1, s2)) # 输出: 'ace'
```
这个函数首先创建一个`dp`矩阵,并初始化所有元素为0。然后逐行逐列遍历字符串`s1`和`s2`,如果当前字符相同,则将上一格的最长公共子串长度加1;如果不相同,则从头开始计算。最后返回找到的最大公共子串。
阅读全文