最长公共子串c++动态规划

最长公共子串问题可以使用动态规划来解决。具体来说，我们可以定义一个二维数组dp，其中dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的最长公共子串的长度。则状态转移方程为：

if (s1[i-1] == s2[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = 0;
}

最终的答案即为dp数组中的最大值。时间复杂度为O(m*n)，其中m和n分别为两个字符串的长度。

相关问题

最长公共子串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`中的结束索引。最后，我们通过提取最长公共子串的方式得到最终的结果。

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

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

c++动态规划法求最长公共子串

最长公共子串问题可以用动态规划算法求解。

假设有两个字符串s1和s2，它们分别有m和n个字符。定义一个二维数组dp，其中dp[i][j]表示以s1[i-1]和s2[j-1]结尾的最长公共子串的长度。则有以下状态转移方程：

当s1[i-1] == s2[j-1]时，dp[i][j] = dp[i-1][j-1] + 1；

当s1[i-1] != s2[j-1]时，dp[i][j] = 0；

其中，dp[i][j] = 0表示以s1[i-1]和s2[j-1]结尾的最长公共子串的长度为0。

最终，最长公共子串的长度即为dp数组中的最大值。同时，可以通过记录最大值所在的位置，找到最长公共子串。

下面是C++代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int dp[MAXN][MAXN];

int main() {
    string s1, s2;
    cin >> s1 >> s2;

    int m = s1.size(), n = s2.size();
    int maxLen = 0, end = 0;

    memset(dp, 0, sizeof(dp));

    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] > maxLen) {
                    maxLen = dp[i][j];
                    end = i-1;
                }
            }
        }
    }

    string ans = s1.substr(end - maxLen + 1, maxLen);
    cout << ans << endl;

    return 0;
}