pytuon中输出两个字符串的最长公共子串的长度

可以使用动态规划的思想来解决这个问题，具体的实现过程如下：

def longest_common_substring(s1, s2):
    m = len(s1)
    n = len(s2)
    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 s1[i-1] == s2[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

其中，dp[i][j]表示以s1[i-1]和s2[j-1]结尾的最长公共子串的长度。如果s1[i-1]和s2[j-1]相等，则dp[i][j] = dp[i-1][j-1] + 1；否则，dp[i][j] = 0。最后返回dp数组中的最大值，即为最长公共子串的长度。

相关问题

pytuon中输出两个字符串的最长公共子串

可以使用动态规划的方法来解决这个问题。

首先创建一个二维数组 `dp`，其中 `dp[i][j]` 表示以字符串 `1` 中第 `i` 个字符、字符串 `2` 中第 `j` 个字符结尾的最长公共子串的长度。

然后遍历字符串 `1` 和字符串 `2` 中的所有字符，如果当前字符相同，则有：

dp[i][j] = dp[i-1][j-1] + 1

如果当前字符不同，则有：

dp[i][j] = 0

遍历过程中，记录最长的公共子串长度 `max_len` 和对应的结束位置 `end_pos`，即：

if dp[i][j] > max_len:
    max_len = dp[i][j]
    end_pos = i

最后，最长公共子串即为字符串 `1` 中以 `end_pos` 结尾的 `max_len` 个字符。

下面是完整的代码实现：

def lcs(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    max_len, end_pos = 0, 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end_pos = i
            else:
                dp[i][j] = 0
    return str1[end_pos-max_len:end_pos]

可以使用以下代码进行测试：

s1 = 'abcdefg'
s2 = 'ababcdf'
print(lcs(s1, s2)) # 输出 'abcd'

两个字符串的最长公共子串

最长公共子串是指在两个字符串中同时出现的最长的子串。可以使用动态规划的方法来解决这个问题。首先，定义一个二维数组dp，其中dp[i][j]表示以字符串str1的第i个字符和字符串str2的第j个字符结尾的最长公共子串的长度。接下来，我们可以使用如下的状态转移方程来计算dp[i][j]的值：
如果str1[i]等于str2[j]，则dp[i][j] = dp[i-1][j-1] + 1；
否则，dp[i][j] = 0。
通过计算dp数组中的每个元素，我们可以得到最长公共子串的长度。然后，我们可以根据dp数组的值来构造最长公共子串。具体的步骤如下：
1. 创建一个变量maxLen来存储最长公共子串的长度，创建一个变量end来存储最长公共子串的结束位置。
2. 遍历dp数组，找到最大的值maxLen和对应的位置end。
3. 根据maxLen和end，从str1中截取最长公共子串并输出。

举个例子来说明这个过程，假设有两个字符串str1 = "abcdefg"和str2 = "defabcd"。根据上述的动态规划方法，我们可以得到如下的dp数组：
d e f a b c d
a 0 0 0 1 0 0 0
b 0 0 0 0 2 0 0
c 0 0 0 0 0 3 0
d 0 0 0 0 0 0 4
e 0 1 0 0 0 0 0
f 0 0 2 0 0 0 0
g 0 0 0 0 0 0 0
其中，最大的值为4，对应的位置为dp，即最长公共子串的结束位置为str1的第3个字符和str2的第6个字符。因此，最长公共子串为"abcd"。

所以，对于给定的两个字符串str1和str2的最长公共子串是"abcd"。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [找出两个字符串的最长公共子串](https://blog.csdn.net/qq_40241957/article/details/124289935)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [python练习 ---求2个字符串的最长公共子串的三种求解方法](https://blog.csdn.net/qq_40498551/article/details/90212272)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]