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

最长公共子串是指在两个字符串中同时出现的最长的子串。可以使用动态规划的方法来解决这个问题。首先，定义一个二维数组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 ]