给定两个字符串，求出它们两个最长的相同子字符串的长度。

这个问题可以使用动态规划来解决。我们可以定义一个二维数组dp，其中dp[i][j]表示以第一个字符串的第i个字符和第二个字符串的第j个字符结尾的最长相同子字符串的长度。如果两个字符不相同，则dp[i][j]为0。如果两个字符相同，则dp[i][j]等于dp[i-1][j-1]+1。最后，我们只需要遍历整个dp数组，找到其中的最大值即可。

以下是代码实现：

int longestCommonSubstring(string s1, string s2) {
int m = s1.size(), n = s2.size();
vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
int ans = 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]);
}
}
}
return ans;
}

相关问题

最长公共子序列问题：给定两个字符串，求它们的最长公共子序列

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

定义一个二维数组 dp，其中 dp[i][j] 表示字符串 s1 的前 i 个字符和字符串 s2 的前 j 个字符的最长公共子序列的长度。

状态转移方程如下：

当 s1[i-1] == s2[j-1] 时，说明当前字符可以作为最长公共子序列的一部分，因此 dp[i][j] = dp[i-1][j-1] + 1。

当 s1[i-1] != s2[j-1] 时，说明当前字符不能作为最长公共子序列的一部分，因此需要去掉 s1 的最后一个字符或者去掉 s2 的最后一个字符，取它们的最大值，即 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

最终结果为 dp[m][n]，其中 m 和 n 分别为字符串 s1 和 s2 的长度。

以下是 Python 代码实现：

def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

例如，对于字符串 s1 = "abcde" 和 s2 = "ace"，最长公共子序列为 "ace"，长度为 3。

问题 1：最长公共子序列（LCS）给定两个字符串 X 和 Y，找出它们的最长公共子序列的长度。最长公共子序列是指两个序列的公共子序列中长度最长的一个。输入：两个字符串 X 和 Y（长度不超过 100）用c语言实现

在C语言中，可以使用动态规划（Dynamic Programming）算法来解决最长公共子序列（LCS）问题。这里给出一个简单的递推函数实现：

#include <stdio.h>
#include <string.h>

int lcs(char *X, char *Y, int m, int n) {
    int L[m + 1][n + 1];
    int i, j;

    // 初始化第一行和第一列
    for (i = 0; i <= m; i++) {
        L[i][0] = 0;
    }
    for (j = 0; j <= n; j++) {
        L[0][j] = 0;
    }

    // 动态填充L数组
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1]) {
                L[i][j] = L[i - 1][j - 1] + 1;
            } else {
                L[i][j] = max(L[i - 1][j], L[i][j - 1]);
            }
        }
    }

    return L[m][n]; // 返回最长公共子序列的长度
}

int main() {
    char X[] = "ABCBDAB";
    char Y[] = "BDCAB";    
    int m = strlen(X);
    int n = strlen(Y);

    printf("Length of LCS is %d\n", lcs(X, Y, m, n));
    return 0;
}

在这个代码中，`lcs()` 函数计算了 `X` 和 `Y` 的最长公共子序列长度，并通过 `max()` 函数处理 `X[i - 1]` 与 `Y[j - 1]` 不相等的情况。