最长公共子串,题目描述：a b两个字符串，求a b的最长公共子串长度，输出最长公共子串长度。子串与子序列不同，子串必须是连续的，而子序列可以不连续。求python代码

好的，以下是Python代码实现：

def longest_common_substring(a, b):
    m, n = len(a), len(b)
    # 初始化dp数组
    dp = [[0] * (n+1) for _ in range(m+1)]
    # 初始化最长公共子串长度
    max_len = 0
    # 遍历a和b的每个字符
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                max_len = max(max_len, dp[i][j])
            else:
                dp[i][j] = 0
    # 返回最长公共子串长度
    return max_len

其中，a和b分别表示输入的两个字符串。使用双重循环遍历a和b的每个字符，并根据定义的dp数组进行动态规划。最后返回最长公共子串长度即可。

相关问题

最长公共子串,题目描述：a b两个字符串，求a b的最长公共子串长度，输出最长公共子串长度

好的，这是一道经典的字符串算法题目。最长公共子串问题可以通过动态规划的方式求解，具体思路如下：

设 $dp[i][j]$ 表示以 $a[i]$、$b[j]$ 结尾的最长公共子串长度，即：

$$
dp[i][j] = \begin{cases} 0, & i=0 \text{ 或 } j=0 \\ dp[i-1][j-1]+1, & a[i]=b[j] \\ 0, & a[i] \neq b[j] \end{cases}
$$

其中，当 $a[i]=b[j]$ 时，$dp[i][j]$ 取决于 $dp[i-1][j-1]$，表示此时最长公共子串长度加一；当 $a[i]\neq b[j]$ 时，$dp[i][j]$ 必然为零，因为以 $a[i]$、$b[j]$ 结尾的字符串不可能存在公共子串。

最终答案即为 $dp$ 数组中的最大值。时间复杂度为 $O(n^2)$，其中 $n$ 是字符串长度。

代码如下：

最长公共子串,题目描述：a b两个字符串，求a b的最长公共子串长度，输出最长公共子串长度。子串与子序列不同，子串必须是连续的，而子序列可以不连续。

好的，这道题目需要求解的是最长公共子串问题，与最长公共子序列问题有所不同。最长公共子串问题可以通过动态规划的方式求解，具体思路如下：

设 $dp[i][j]$ 表示以 $a[i]$、$b[j]$ 结尾的最长公共子串长度，即：

$$
dp[i][j] = \begin{cases} 0, & i=0 \text{ 或 } j=0 \\ dp[i-1][j-1]+1, & a[i]=b[j] \\ 0, & a[i] \neq b[j] \end{cases}
$$

其中，当 $a[i]=b[j]$ 时，$dp[i][j]$ 取决于 $dp[i-1][j-1]$，表示此时最长公共子串长度加一；当 $a[i]\neq b[j]$ 时，$dp[i][j]$ 必然为零，因为以 $a[i]$、$b[j]$ 结尾的字符串不可能存在公共子串。

最终答案即为 $dp$ 数组中的最大值。时间复杂度为 $O(n^2)$，其中 $n$ 是字符串长度。

代码如下：

def longest_common_substring(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n+1) for _ in range(m+1)]
    max_len = 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                max_len = max(max_len, dp[i][j])
            else:
                dp[i][j] = 0
    return max_len

如果需要输出最长公共子串，可以记录最长公共子串的结束位置，然后通过结束位置和最长公共子串长度计算出起始位置：

def longest_common_substring(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n+1) for _ in range(m+1)]
    end, max_len = 0, 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end = i - 1
            else:
                dp[i][j] = 0
    start = end - max_len + 1
    return a[start:end+1]