输入两个字符串,获取两个字符串中公共的子字符串。
时间: 2023-05-11 10:04:54 浏览: 94
可以使用动态规划算法来解决这个问题。具体步骤如下:
1. 定义一个二维数组dp,其中dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的公共子字符串的长度。
2. 初始化dp数组,将第一行和第一列都赋值为0。
3. 遍历两个字符串,如果第一个字符串的第i个字符和第二个字符串的第j个字符相等,则dp[i][j] = dp[i-1][j-1] + 1,否则dp[i][j] = 0。
4. 在遍历的过程中记录最长的公共子字符串的长度和结束位置。
5. 根据最长公共子字符串的长度和结束位置,可以得到公共子字符串。
以下是代码实现:
```python
def find_common_substring(str1, str2):
m, n = len(str1), len(str2)
dp = [[0] * (n+1) for _ in range(m+1)]
max_len, end_pos = 0, 0
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
else:
dp[i][j] = 0
return str1[end_pos-max_len:end_pos]
```
例如,对于输入的字符串"abcdefg"和"bcdefgh",输出为"bcdefg"。