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;
}