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

这个问题可以使用动态规划来解决。我们可以定义一个二维数组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。

给定一个字符串找出最长不包含重复字段子符号的长度

好的，这是一个经典的算法问题，我可以帮你解答。该问题可以使用滑动窗口算法来解决。

具体来说，我们可以使用两个指针start和end来表示当前子字符串的起始位置和结束位置，然后使用一个哈希表来记录每个字符最后一次出现的位置。

我们遍历字符串，当当前字符上次出现的位置在start之后时，更新start为上次出现位置的下一个位置；否则更新最长不包含重复字段子符号的长度为当前子字符串长度和历史最长长度的最大值，并将当前字符的位置记录在哈希表中。

以下是代码实现：

def longest_substring_without_duplication(s):
    if not s:
        return 0
    
    start = 0
    max_len = 0
    char_index = {}
    
    for i in range(len(s)):
        if s[i] in char_index and char_index[s[i]] >= start:
            start = char_index[s[i]] + 1
        char_index[s[i]] = i
        max_len = max(max_len, i - start + 1)
    
    return max_len

希望这个答案能够帮到你！