c++动态规划最大公共子串
时间: 2023-10-13 17:09:41 浏览: 57
动态规划可以用来解决最大公共子串的问题,其基本思想是利用已计算出的子问题的解来求解更大的问题。
下面是一个C++实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
int main() {
string s1, s2;
cin >> s1 >> s2;
int len1 = s1.length(), len2 = s2.length();
int dp[len1 + 1][len2 + 1], ans = 0;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
ans = max(ans, dp[i][j]);
}
}
}
cout << ans << endl;
return 0;
}
```
在上面的代码中,我们使用了一个二维数组 `dp` 来存储最大公共子串的长度,其中 `dp[i][j]` 表示以 `s1` 的第 `i` 个字符和 `s2` 的第 `j` 个字符为结尾的最大公共子串的长度。当 `s1[i-1] == s2[j-1]` 时,说明 `s1` 和 `s2` 的第 `i` 和 `j` 个字符相同,那么最大公共子串的长度就可以加1,即 `dp[i][j] = dp[i-1][j-1] + 1`。同时,我们需要维护一个变量 `ans` 来记录最大的公共子串长度。
最后,输出 `ans` 即可得到最大公共子串的长度。
相关推荐
![](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)
![](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)