最长公共子串的长度 描述:给定两个字符串str1和str2,输出两个字符串的最长公共子串的长度(假设str1和str2的最长公共子串存在且唯一)。
时间: 2024-01-07 17:50:58 浏览: 110
输入两个字符串,求它们最长公共字串的长度
5星 · 资源好评率100%
最长公共子串问题可以使用动态规划求解。
定义一个二维数组dp,其中dp[i][j]表示以str1[i]和str2[j]结尾的最长公共子串的长度。如果str1[i]和str2[j]不相等,则dp[i][j]=0;如果相等,则有dp[i][j]=dp[i-1][j-1]+1。
最终的最长公共子串的长度就是dp数组中的最大值。
以下是Python代码实现:
```python
def longest_common_substring(str1, str2):
m, n = len(str1), len(str2)
dp = [[0] * n for _ in range(m)]
max_len = 0
for i in range(m):
for j in range(n):
if str1[i] == str2[j]:
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = dp[i-1][j-1] + 1
max_len = max(max_len, dp[i][j])
return max_len
```
例如,对于字符串"abcdefg"和"bcdeff",最长公共子串为"bcdef",长度为5。
阅读全文