c++ 最长公共子串
时间: 2023-11-03 21:53:42 浏览: 49
最长公共子串是指在两个字符串中找到最长的相同连续子序列。这个问题可以通过动态规划来解决。首先,我们定义一个二维数组dp,其中dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的最长公共子串的长度。
算法步骤如下:
1. 初始化dp数组的第一行和第一列为0。
2. 遍历两个字符串的每个字符,如果两个字符相等,即str1[i-1] == str2[j-1],则更新dp[i][j]为dp[i-1][j-1] + 1。
3. 如果两个字符不相等,则dp[i][j]为0,表示当前位置没有公共子串。
4. 在遍历过程中,记录最长公共子串的长度以及其结束位置。
5. 返回最长公共子串。
下面是一个示例代码实现:
```python
def longest_common_substring(str1, str2):
m = len(str1)
n = len(str2)
max_len = 0 # 记录最长公共子串的长度
end_pos = 0 # 记录最长公共子串的结束位置
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
if dp[i][j] > max_len:
max_len = dp[i][j]
end_pos = i - 1
longest_substring = str1[end_pos - max_len + 1: end_pos + 1]
return longest_substring
# 示例用法
str1 = "abcdefg"
str2 = "bcde"
result = longest_common_substring(str1, str2)
print(result) # 输出 "bcde"
```
这样,我们可以找到两个字符串的最长公共子串。希望能帮到你!