最长公共子串C++代码

以下一个使用动态规划算法求最长公共子串（Longest Common Substring）的C++代码示例：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

string LongestCommonSubstring(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();

    // 创建二维动态规划数组
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    int maxLength = 0;  // 最长公共子串的长度
    int endIndex = 0;   // 最长公共子串在s1中的结束索引

    // 动态规划计算公共子串长度
    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;
                if (dp[i][j] > maxLength) {
                    maxLength = dp[i][j];
                    endIndex = i - 1;
                }
            }
        }
    }

    // 提取最长公共子串
    string longestSubstring = s1.substr(endIndex - maxLength + 1, maxLength);

    return longestSubstring;
}

int main() {
    string s1, s2;
    cout << "请输入字符串s1：";
    cin >> s1;
    cout << "请输入字符串s2：";
    cin >> s2;

    string longestSubstring = LongestCommonSubstring(s1, s2);

    cout << "最长公共子串为：" << longestSubstring << endl;

    return 0;
}

在示例代码中，我们使用动态规划的思想来解决最长公共子串的问题。我们创建一个二维动态规划数组`dp`，其中`dp[i][j]`表示以`s1[i-1]`和`s2[j-1]`为结尾的最长公共子串的长度。然后，我们遍历字符串`s1`和`s2`的所有字符，如果当前字符相等，则将`dp[i][j]`更新为`dp[i-1][j-1] + 1`，同时记录最长公共子串的长度和在`s1`中的结束索引。最后，我们通过提取最长公共子串的方式得到最终的结果。

请注意，以上代码仅考虑了求解最长公共子串的长度和提取最长公共子串，如果需要其他操作（如输出所有最长公共子串），可能需要进行适当的修改。

希望对你有帮助！如果你有任何问题，请随时提问。