首页 > 试题广场 >

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

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

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

$\hspace{15pt}$ 对于给定的两个字符串 $s$ 和 $t$ ，你需要找出它们的最长公共子串。特别地，如果存在多个答案，输出在较短串中最先出现的那个。

$\hspace{15pt}$ 子串为从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。
$\hspace{15pt}$ 如果字符串 $a$ 的一个子串 $a'$ 与字符串 $b$ 的一个子串 $b'$ 完全相等，那么子串 $a',b'$ 是字符串 $a,b$ 的一个公共子串。

输入描述:

第一行输入一个长度为 、仅由小写字母组成的字符串 。
第二行输入一个长度为 、仅由小写字母组成的字符串 。

输出描述:

输出一个字符串，代表  和  的最长公共子串。如果存在多个答案，输出在较短串中最先出现的那个。

示例1

输入

awaabb
aawbb

输出

aa

说明

在这个样例中， 和  都是  和  的最长公共子串，但  在较短串  中首先出现，因此输出 。

示例2

输入

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 展开全文

godhands

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

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

小陆要懂云

发表于 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()) { 展开全文

牛客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 展开全文

量力而不行

发表于 2022-04-20 11:01:42

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

牛客949327122号

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

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

法拉利201903231900848

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

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

问题信息

字符串

难度：

504条回答 2532收藏 64805浏览

通过挑战的用户

查看代码

AHAHAHAHA6

2023-03-06 11:17:33
奈何笑不了

2023-03-02 16:44:55
牛客15248...

2023-01-25 02:03:36
思钱想厚008

2023-01-08 00:27:36
梧桐上的小鸟

2022-12-18 16:00:23

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

输入描述:

输出描述:

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题