最长公共子串

[编程题]最长公共子串

热度指数：189439 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

数据范围： $1 \le |str1|,|str2| \le 5000$
要求：空间复杂度 $O(n^2)$ ，时间复杂度 $O(n^2)$

示例1

输入

"1AB2345CD","12345EF"

输出

"2345"

备注:

算法知识视频讲解

数据结构和算法

发表于 2021-07-05 09:30:15

精华题解动态规划解决注意这题求的是最长公共子串，不是最长公共子序列，子序列可以是不连续的，但子串一定是连续的。定义dp[i][j]表示字符串str1中第i个字符和str2种第j个字符为最后一个元素所构成的最长公共子串。如果要求dp[i][j]，也就是str1的第i个字符和str2的第j个字符为最后一个元展开全文

牛客题解官

发表于 2022-04-22 12:40:18

精华题解题目主要信息：查找两个字符串str1，str2中的最长的公共子串保证str1和str2的最长公共子串存在且唯一举一反三：学习完本题的思路你可以解决如下题目： BM65 最长公共子序列(二) BM71.最长上升子序列(一) BM73 最长回文子串 BM75 编辑距离(一) BM76 正则表展开全文

士大夫色弱

发表于 2020-11-08 21:38:15

最长公共子串题目描述给定两个字符串str1和str2,输出两个字符串的最长公共子串，如果最长公共子串为空，输出-1。示例1输入"1AB2345CD","12345EF"返回值"2345" 这条题目被归类为动态规划，于是我使用动态规划的思路写了一个算法： /** * longest 展开全文

Arktische

发表于 2020-11-18 10:05:13

思路一看到两个字符串的“最值”问题，一般想到二维dp。很自然地想到把str1前i个字符和str2前j个字符最长公共子串的长度作为dp[i][j]，但由于子串定义必须是原字符串连续的序列，这样定义无法找到递推关系，因此需要加限定条件——以str1[i-1]和str2[j-1]结尾的最长公共子串长度。展开全文

小青年201909292117791

发表于 2022-03-15 19:51:07

滑窗这样写可能更加直接一点吧， 1.首先给字符串1定义一个头指针，然后比较str1[left,i]这个子字符串是否在串2中，若在赋值给res 2.若不在，则将left+1，继续向后移动，直到结束 # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # longest c 展开全文

一株木棉1

发表于 2021-01-05 19:18:10

两种实现方式可以优化哦！第一种字符串包含，内存占用较大 maxlen :记录最长字串的长度 index：最长字串的下标思路: str1 包含str2 中的最长字串展开全文

Lanerx

发表于 2021-09-23 20:04:40

import java.util.*; public class Solution { /** * longest common substring * @param str1 string字符串 the string * @param str2 strin 展开全文

alfred_fomo

发表于 2021-02-27 12:52:50

可以参考leetcode上面的【1143. 最长公共子序列】（https://leetcode-cn.com/problems/longest-common-subsequence/solution/1143-zui-chang-gong-gong-zi-xu-lie-dong-zde2v/）区展开全文

总之就是非常菜

发表于 2021-01-09 16:58:15

思路最长公共子串是两个字符串最长相同的连续子序列；最长公共子序列是两个字符串最长相同的可非连续子序列，思路可以和最长公共子序列一样(动态规划经典例题——最长公共子序列和最长公共子串 )，但是仅仅用二维数组只能得到递推关系，即当前最优解为上一个解+1：dp[i][j]=dp[i-1][j-1],无法确展开全文