两个字符串，求最长公共子串完整代码

以下是求最长公共子串的完整代码：

#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];
memset(dp, 0, sizeof(dp));
int ans = 0, end = 0;
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;
if (dp[i][j] > ans) {
ans = dp[i][j];
end = i - 1;
}
}
}
}
cout << s1.substr(end - ans + 1, ans) << endl;
return 0;
}

如果您有任何问题，请随时问我。

相关问题

求两个字符串的最长公共子串

可以使用动态规划来解决最长公共子串的问题。

假设给出两个字符串 $s1$ 和 $s2$，用 $dp[i][j]$ 表示以 $s1$ 的第 $i$ 个字符和 $s2$ 的第 $j$ 个字符为结尾的最长公共子串的长度。

当 $s1[i] \neq s2[j]$ 时，$dp[i][j]$ 应该为 0，因为以这两个字符结尾的字符串不可能有公共子串。

当 $s1[i] = s2[j]$ 时，$dp[i][j]$ 应该为 $dp[i-1][j-1] + 1$，因为以这两个字符结尾的字符串可能有公共子串，并且公共子串的长度就是 $dp[i-1][j-1]$ 加上 1。

最终的答案就是 $dp[i][j]$ 中的最大值。

下面是该问题的 Python 代码实现：

def longest_common_substring(s1, s2):
    n1, n2 = len(s1), len(s2)
    dp = [[0] * (n2+1) for _ in range(n1+1)]
    ans = 0
    for i in range(1, n1+1):
        for j in range(1, n2+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                ans = max(ans, dp[i][j])
    return ans

时间复杂度为 $O(n_1n_2)$，其中 $n_1$ 和 $n_2$ 分别是两个字符串的长度。

python求两个字符串的最长公共子串

可以使用动态规划来解决这个问题。

具体思路是，用一个二维数组记录两个字符串的所有子串的匹配情况，然后找到所有匹配的子串中最长的一个即可。

下面是 Python 代码实现：

def find_longest_common_substring(str1, str2):
    m = len(str1)
    n = len(str2)
    # 构建二维数组，记录子串匹配情况
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    max_len = 0
    end = 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 = i
            else:
                dp[i][j] = 0
    # 返回最长公共子串
    return str1[end - max_len:end]

使用该函数可以得到两个字符串的最长公共子串，例如：

str1 = "abcdefg"
str2 = "defg1234"
longest_common_substring = find_longest_common_substring(str1, str2)
print(longest_common_substring)  # 输出 "defg"