首页 > 试题广场 >

公共子串计算

[编程题]公共子串计算

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

$\hspace{15pt}$ 对于给定的两个字符串 $s$ 和 $t$ ，你需要找出它们的最长公共子串的长度。

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

输入描述:

$\hspace{15pt}$ 第一行输入一个长度为 $1 \leqq {\rm len}(s) \leqq 150$ 、仅由小写字母组成的字符串 $s$ 。
$\hspace{15pt}$ 第二行输入一个长度为 $1 \leqq {\rm len}(t) \leqq 150$ 、仅由小写字母组成的字符串 $t$ 。

输出描述:

$\hspace{15pt}$ 输出一个整数，代表 $s$ 和 $t$ 的最长公共子串的长度。

示例1

输入

awaabb
aawbb

输出

说明

在这个样例中， 和  都是  和  的最长公共子串。

示例2

输入

asdfas
werasdfaswer

输出

算法知识视频讲解

牛客834002708号

发表于 2021-08-13 23:23:49

import java.util.*; public class Main { public static void main(String[] args) { 展开全文

不会做题的小菜鸡

发表于 2021-12-06 23:34:21

题目分析题目给出两个字符串要求我们输出两个字符串中的最长的公共子串的长度方法一：暴力匹配实现思路从较短的字符串s1中暴力获取所有的子串然后将每一个子串在s2中进行匹配，如果存在s2中而且长度比之前找到的公共子串更长，则更新mxlen 最终返回mxlen值 def sol 展开全文

BSF

发表于 2021-10-14 22:18:55

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

牛客892148583号

发表于 2022-04-07 00:51:35

动态规划求解：最长公共子串区分最长公共子串/子序列 (百度) str1 与 str2 某个字符相同时，要找到没有它们参与时前面的最优解dp[i-1][j-1] 此时再 + 1 得到dp[i][j] = dp[i-1][j-1] + 1; import java.util.Scanne 展开全文

小陆要懂云

发表于 2021-08-20 16:01:01

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

未来0116

发表于 2021-12-09 20:58:53

HJ75公共子串计算一.题目描述给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。二.算法一(暴力) 由于是字串是个连续的字符串，我们可以暴力循环的方法查找截取出长串的所有字串，判断其是否会在短串展开全文

牛客44738297号

发表于 2021-02-21 17:51:14

while True: try: a = input() b = input() if len(a) > len(b): a,b = b,a max_length = 0 i = 0 展开全文

迪士尼在逃米老鼠

发表于 2020-02-23 19:05:56

这道题考的是常见的最长公共子串问题，这类问题需要用动态规划解决。 dp[i][j] 表示字符串a[1...i]和字符串b[1...j]的最大公共字串长度。递推公式：如果a[i] == a[j]，那么dp[i][j] = dp[i-1][j-1] + 1; 否则 dp[i][j] = 0； #in 展开全文