C++实现输入两个字符串，找两个字符串公共子串

在C++中，我们可以使用动态规划的方法来找到两个字符串之间的最长公共子串。这里是一个简单的实现步骤：

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

std::string longestCommonSubstring(const std::string& s1, const std::string& s2) {
    int m = s1.length();
    int n = s2.length();

    // 创建一个二维数组来存储中间结果
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

    int maxLength = 0;
    int endPos = -1;

    // 遍历s1和s2
    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];
                    endPos = i - 1; // 当前结束位置
                }
            }
        }
    }

    // 根据endPos回溯构建最长公共子串
    std::string result(endPos - maxLength + 1, ' ');
    s1.copy(result.begin(), endPos + 1, endPos + 1 - maxLength);
    return result;
}

int main() {
    std::string str1 = "hello";
    std::string str2 = "worldhello";
    std::cout << "Longest common substring is: " << longestCommonSubstring(str1, str2) << std::endl;
    return 0;
}

在这个程序中，我们首先初始化一个动态规划矩阵`dp`，然后通过双层循环比较两个字符串的每个字符。如果字符相同，就将上一行和上一列的值加一，并检查是否更新了当前找到的最大公共子串的长度。最后，返回最长公共子串。