什么是公共子串呢?For example,对于abcdefg与aaabcddefgefg,有多个相同的子序列,例如abcd,defg,efg,那就输出abcd(如果子序列长度相等,输出先出现的)哈哈,很简单吧,那就解决它吧。c
时间: 2023-06-12 14:08:23 浏览: 37
好的,这个问题可以使用动态规划来解决。我们可以定义一个二维的 dp 数组,其中 dp[i][j] 表示以字符串 A 的第 i 个字符和字符串 B 的第 j 个字符结尾的公共子串的长度。
转移方程为:
dp[i][j] = dp[i-1][j-1] + 1 (如果 A[i] == B[j])
dp[i][j] = 0 (如果 A[i] != B[j])
其中,如果 A[i] == B[j],说明当前字符能够构成公共子串,那么我们就在 dp[i-1][j-1] 的基础上加上 1,即可得到 dp[i][j]。如果 A[i] != B[j],那么当前字符不能构成公共子串,所以 dp[i][j] 就置为 0。
最后,我们遍历 dp 数组,找到最长的公共子串即可。
以下是 C++ 代码实现:
```c++
#include <iostream>
#include <string>
using namespace std;
int main()
{
string A, B;
cin >> A >> B;
int m = A.size();
int n = B.size();
int maxLen = 0; // 最长公共子串的长度
int end = 0; // 最长公共子串在 A 串中的结束位置
int dp[m+1][n+1]; // 定义 DP 数组
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
{
if (A[i-1] == B[j-1])
{
dp[i][j] = dp[i-1][j-1] + 1;
if (dp[i][j] > maxLen)
{
maxLen = dp[i][j];
end = i - 1;
}
}
}
}
cout << A.substr(end - maxLen + 1, maxLen) << endl; // 输出最长公共子串
return 0;
}
```