利用动态规划算法求最长公共子串

最长公共子串问题可以通过动态规划算法来解决。

假设有两个字符串S1和S2，它们的长度分别为m和n。定义dp[i][j]为S1以第i个字符结尾、S2以第j个字符结尾的最长公共子串的长度。

那么，当S1[i] == S2[j]时，dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = 0。

最后，我们只需要在dp数组中找到最大值即可。

详细的动态规划算法实现如下：

int longestCommonSubstring(string s1, string s2) {
    int m = s1.length();
    int n = s2.length();
    int dp[m+1][n+1];
    int ans = 0;
    memset(dp, 0, sizeof(dp)); // 初始化dp数组为0
    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;
                ans = max(ans, dp[i][j]);
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return ans;
}

其中，max()函数用于求最大值，memset()函数用于初始化数组为0。