我要招人

去企业版

首页 > 试题广场 >

查找两个字符串a,b中的最长公共子串

[编程题]查找两个字符串a,b中的最长公共子串

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

查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。

注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！

数据范围：字符串长度 $1\le length \le300 \$

进阶：时间复杂度： $O(n^3)\$ ，空间复杂度： $O(n)\$

输入描述:

输入两个字符串

输出描述:

返回重复出现的字符

示例1

输入

abcdefghijklmnop
abcsafjklmnopqrstuvw

输出

jklmnop

算法知识视频讲解

BSF

发表于 2021-10-14 18:32:58

while True: try: a, b = input(), input() # a保存短，b保存长 if len(a) > len(b): a, b = b, a res = '' for i 展开全文

江南好___

发表于 2021-12-09 17:53:17

描述题目描述查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！示例输入： abcdefghijklmnop abcsafjklmnopqrstuvw 输出： jklm 展开全文

小陆要懂云

发表于 2021-08-20 16:36:53

#include <bits/stdc++.h> using namespace std; string LCS(string str1, string str2) { // write code here if(str1.size()>str2.s 展开全文

牛客568583966号

发表于 2022-03-09 15:22:32

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { 展开全文

godhands

发表于 2021-12-09 23:59:59

题目简述首先给我们两个字符串，一个命名为a，一个命名为b，然后我们要做的事情就是，找到这两个字符串中的最长的一个公共子串，然后输出这里需要注意的是，子串是要连续的一串，然而子序列是我们中间是可以有中断的样例解释样例输入 abcdefghijklmnop abcsafjklmnopqrstuv 展开全文

牛客940206908号

发表于 2021-10-07 22:23:24

#用动态规划来解 # while True: try: s1 = input() s2 = input() m = len(s1) n = len(s2) #使s1为最短长度字符串，在搜索过程后，处于外循环，可以展开全文

王琨琨

发表于 2021-11-15 21:02:23

#include<stdio.h> #include<string.h> int main() { char str1[1000],str2[1000],ans[1000]; &nbs 展开全文

法拉利201903231900848

发表于 2019-08-23 00:17:05

while True: try: s1=input() &nb 展开全文

牛客949327122号

发表于 2022-10-11 14:27:12

动态规划 A 、B数组各抽出一个前缀子数组，单看它们的末尾项，如果它们俩不一样——以它们俩为末尾项形成的公共子数组的长度为0：dp[i][j] = 0 如果它们俩一样，以它们俩为末尾项的公共子数组，长度保底为1——dp[i][j]至少为 1，要考虑它们俩的前缀数组——dp[i-1][j-1]能为它们展开全文