根据动态规划的思想完成LCSubstring方法,求出给定两个字符串的最长公共子串长度。写出python代码
时间: 2024-11-30 17:29:31 浏览: 19
要使用动态规划解决两个字符串的最长公共子串(Longest Common Substring, LCS)问题,你可以编写如下的Python代码:
```python
def LCSubstring(str1, str2):
len1, len2 = len(str1), len(str2)
# 初始化二维数组c
c = [[0] * (len2 + 1) for _ in range(len1 + 1)]
# 记录最长公共子串长度和结束位置
max_len = 0
end_pos = 0
# 填充二维数组c
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
if str1[i - 1] == str2[j - 1]:
c[i][j] = c[i - 1][j - 1] + 1
if c[i][j] > max_len:
max_len = c[i][j]
end_pos = i
else:
c[i][j] = 0
# 返回最长公共子串长度
return max_len
# 示例
str1 = "abcdefg"
str2 = "xyzabcfghijk"
length = LCSubstring(str1, str2)
print(f"最长公共子串长度为: {length}")
```
这段代码首先创建了一个二维数组`c`来存储子串长度,然后通过遍历两个字符串,如果当前字符相同,则更新`c`的对应元素并更新最长子串信息;如果不相同,则置`c`的元素为0。最后返回最长公共子串的长度。
阅读全文