首页 > 试题广场 >

最长公共子串

[编程题]最长公共子串
  • 热度指数：7861 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定两个字符串str1和str2,输出两个字符串的最长公共子串，如果最长公共子串为空，输出-1。

输入描述:
输入包括两行，第一行代表字符串srr1，第二行代表字符串str2。


输出描述:
输出包括一行，代表最长公共子串。
示例1

输入

1AB2345CD
12345EF

输出

2345

备注:
时间复杂度，额外空间复杂度。（n可以为其中任意一个字符串长度）
算法知识视频讲解
开通博客
头像 FrankChan
发表于 2020-04-21 22:48:51
图是从左神的书里截的。这个思路很很巧妙。例如当前有如下两个串：a b c d eb e b c d构造图4-10，图中的数值表就是二维dp[i][j]的值。dp[i][j]只与dp[i-1][j-1]有关。每一轮斜线扫描时，开始长度curLen = 0，如果对应i, j的字符相等，则curLen++ 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 总之就是非常可爱
发表于 2022-02-19 17:31:43
    //动态规划，申请一个n行m列的dp数组 //dp[i][j]的含义为必须以str1[i],和str2[j]为结尾的情况下 //最长公共子串的长度是多少 #include<bits/stdc++.h> using namespace std; int main 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 总之就是非常可爱
发表于 2022-02-19 17:41:37
//暴力解 #include<bits/stdc++.h> using namespace std; int main(){     string str1,str2;     cin>>str1>>str2;   展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 戊子仲秋
发表于 2023-04-10 19:32:39
动态规划： #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; string get_str(string 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客722772085号
发表于 2023-10-12 21:09:20
#include <iostream> #include<string> using namespace std; string s1,s2; int maxi=0; int u=0; int dp[5000][5000]; int main() { cin>& 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
上传者：小小
难度：
15条回答 7525浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号