给定2个字符串,试求出这2个字符串的最长公共子串的长度。 输入格式: 输入共2行,每行一个字符串。字符均为小写英文字母。 输出格式: 仅一行,包含一个正整数,表示2个字符串的最长公共子串长度。对于30%的数据,保证字符串长度不超过10; 对于60%的数据,保证字符串长度不超过100; 对于90%的数据,保证字符串长度不超过1000; 对于100%的数据,保证字符串长度不超过5000;
时间: 2024-02-01 10:12:10 浏览: 26
可以使用动态规划来解决这个问题。
假设第一个字符串为s1,第二个字符串为s2,令dp[i][j]表示以s1[i]和s2[j]为结尾的最长公共子串的长度。则有以下状态转移方程:
- 如果s1[i] == s2[j],那么dp[i][j] = dp[i-1][j-1] + 1;
- 如果s1[i] != s2[j],那么dp[i][j] = 0。
最终的结果就是dp数组中的最大值。
代码如下:
相关问题
最长公共子串的长度 描述:给定两个字符串str1和str2,输出两个字符串的最长公共子串的长度(假设str1和str2的最长公共子串存在且唯一)。
最长公共子串问题可以使用动态规划求解。
定义一个二维数组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。
给定两个字符串 和 ,他们的长度分为为和,求出他们的最长公共子串的长度。用c++做这道题目
这道题可以用动态规划来解决。
定义一个二维数组 dp,其中 dp[i][j] 表示以第一个字符串的第 i 个字符和第二个字符串的第 j 个字符结尾的最长公共子串的长度。则最终答案即为所有 dp[i][j] 中的最大值。
状态转移方程为:
- 当 i=0 或 j=0 时,dp[i][j] = 0;
- 当 s1[i-1] == s2[j-1] 时,dp[i][j] = dp[i-1][j-1] + 1;
- 当 s1[i-1] != s2[j-1] 时,dp[i][j] = 0。
根据状态转移方程,可以写出如下代码:
```c++
int longestCommonSubstring(string s1, string s2) {
int m = s1.size(), n = s2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
int maxlen = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxlen = max(maxlen, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return maxlen;
}
```
以上是求最长公共子串长度的代码,如果需要输出最长公共子串本身,可以记录下最长公共子串结束的位置,然后从该位置向前推出最长公共子串。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)