首页 > 试题广场 >

查找两个字符串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

算法知识视频讲解

Python3

虾厂摸鱼哥

s1,s2=input(),input()
#强制s1长度<s2长度
if len(s1)>len(s2):
    s1,s2=s2,s1
sum_len,str=len(s1),''
for i in range(1,sum_len+1):
    for j in range(0,sum_len):
        if s1[j:i] in s2 and len(s1[j:i]) > len(str):#若有多个，输出在较短串中最先出现的那个
            str=s1[j:i]
print(str)

编辑于 2024-04-25 00:08:00 回复(0)

Python3

来泡池子了的柯基很热血

a=input()
b=input()
if len(a)>len(b):
    a,b=b,a
str=''
for i in range(len(a)-1):
    for j in range(len(a),i+1,-1):
        if a[i:j] in b and len(a[i:j])>len(str):
            str=a[i:j]
print(str)

编辑于 2024-03-26 10:43:19 回复(0)

Python3

牛客308721343号

word1 = input()

word2 = input()

if len(word1) >= len(word2):

word1, word2 = word2, word1

list1 = []

list2 = []

for i in range(len(word1)):

for j in range(i + 1, len(word1) + 1):

list1.append(word1[i:j])

for k in range(len(word2)):

for v in range(k + 1, len(word2) + 1):

list2.append(word2[k:v])

list3 = list(set(list1) & set(list2))

sort_list = sorted(list3, key=lambda x: len(x), reverse=True)

max_len = len(sort_list[0])

short_list = None

for l in sort_list:

if len(l) == max_len:

if short_list is None or list1.index(l) < list1.index(short_list):

short_list = l

print(short_list)

发表于 2024-03-22 14:41:49 回复(0)

Python3

牛客561675659号

a,b=input().strip(),input().strip()

#让a时长度较短的哪一个

if len(a)>len(b):

a,b=b,a

c=[]

for i in range(len(a)):

for j in range(i+1,len(a)+1):

if a[i:j] in b:

c.append(a[i:j])

#找到最长公共子串,同时时最先出现的那个

substr=''

for k in c:

if len(k)>len(substr):

substr=k

print(substr)

发表于 2023-09-13 10:03:29 回复(0)

Python3

YM学渣

s1 = input()
s2 = input()
# 让s1为最短
if len(s1) > len(s2):
    s1,s2 = s2,s1
n = len(s1)

res = ''
# 滑窗
r=l=0
while r<n:
    
    if s1[l:r+1] in s2 and r-l+1 > len(res):
        res = s1[l:r+1]
        
    r+=1
    
    while l<r and s1[l:r+1] not in s2:
        l+=1

print(res)

发表于 2023-07-27 14:46:28 回复(0)

Python3

1bit都不剩了

滑窗卷积

# 暴力滑窗
str_i = input()
str_j = input()
if(len(str_i) > len(str_j)): str_i,str_j = str_j,str_i
for i in range(len(str_i)-1): str_j = "\r"+str_j+"\r"

max_len = 0
max_len_pos = -1
for j in range(len(str_j)-len(str_i)+1):
    temp_len = 0
    for i in range(len(str_i)):
        if(str_i[i] == str_j[j+i]):
            temp_len += 1
            if(temp_len > max_len):
                max_len = temp_len
                max_len_pos = i+1-temp_len
            elif(temp_len == max_len):
                head_pos = i+1-temp_len
                if(head_pos < max_len_pos): max_len_pos = head_pos
        else:
            temp_len = 0
#print(max_len_pos)
for i in range(max_len): print(str_i[max_len_pos+i],end = "")

发表于 2023-07-26 19:43:56 回复(0)

Python3

阿常呓语

我想问下，这个要返回子串，如果有多个相同的子串如何返回呢？比较困惑，是返回第一次出现的位置，还是最后一次出现的位置呢？

efgyiffxoonftmmvd

exwzdcwjsttuhsxrcpzplpnfqxqsqtlfctdkgacejitayoafucmfxxhkxyixxykndchyjc

比如这个例子：返回 yi or nf ？这个我比较困惑，

预期输出yi ,但我返回的 nf 但这个也有错吗？题目并没有说明白.

代码放在下面了，有大佬帮忙解释一下吗

# -*- coding: utf-8 -*-
"""
@Time    : 2023/5/19 08:25
@Author  : Frank
@File    : HJ56.py

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


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

数据范围：字符串长度


输入描述：
输入两个字符串



dp 问题

dp


if str1[i - 1] == str2[j - 1]
    dp[i][j] = dp[i - 1][j - 1] + 1
else:
    dp[i][j] = 0



返回公共的字符串 可能有多个。

如下面的例子：
公共子串的长度是3，但是有两个不同的子串
gcn
nlo



nvlrzqcjltmrejybjeshffenvkeqtbsnlocoyaokdpuxutrsmcmoearsgttgyyucgzgcnurfbubgvbwpyslaeykqhaaveqxijc

wkigrnngxehuiwxrextitnmjykimyhcbxildpnmrfgcnevjyvwzwuzrwvlomnlogbptornsybimbtnyhlmfecscmojrxekqmj
"""


def prepare_data():
    str1 = input()
    str2 = input()
    return str1, str2
    pass


def lc_substr(str1, str2):
    n = len(str1)
    m = len(str2)

    dp = [[0 for j in range(m + 1)] for i in range(n + 1)]

    max_len = 0
    index = 0

    # 下标从1开始
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # 注意这里 比较 i-1 and j-1 这个表示当前的字符
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j] >= max_len:
                    max_len = dp[i][j]
                    index = i
            else:
                dp[i][j] = 0

    return str1[index - max_len:index]


if __name__ == '__main__':
    # s = 'abcde'
    # s2 = 'cde'

    s, s2 = prepare_data()
    # s = 'nvlrzqcjltmrejybjeshffenvkeqtbsnlocoyaokdpuxutrsmcmoearsgttgyyucgzgcnurfbubgvbwpyslaeykqhaaveqxijc'
    # s2 = 'wkigrnngxehuiwxrextitnmjykimyhcbxildpnmrfgcnevjyvwzwuzrwvlomnlogbptornsybimbtnyhlmfecscmojrxekqmj'
    print(lc_substr(s, s2))

发表于 2023-05-19 10:13:10 回复(2)

Python3

牛客503925442号

a = input().strip()
b = input().strip()
if len(a) > len(b):
    temp = a
    a = b
    b = temp

max_sub = ''
for i in range(len(a)):
    for j in range(len(a), i, -1):
        if (a[i:j] in b) and (len(max_sub) < len(a[i:j])):
            max_sub = a[i:j]

print(max_sub)

发表于 2023-05-18 15:24:22 回复(1)

Python3

有趣的代码渣渣在吐槽

us1,us2 = input(),input()
ll = []
if len(us1) > len(us2):
    us1,us2 = us2,us1
for _idx in range(len(us1) + 1):
    for j in range(_idx):
        _s = us1[j:_idx]
        if _s in us2:
            ll.append(_s)
print(sorted(ll, key=len, reverse=True)[0])

发表于 2023-04-20 23:16:12 回复(0)

Python3

夢亦飛扬

def max_same_str(a,b):
    c=[]
    d=[]
    for i in range(len(a)):
        for j in range(i+1,len(a)+1):
            if a[i:j] in b:
                c.append(a[i:j])
                d.append(len(a[i:j]))
    x=max(d)
    y=c[d.index(x)]
    print(y)

while True:
    try:
        s1=input()
        s2=input()
        if len(s2)>len(s1):
            max_same_str(s1,s2)
        else:
            max_same_str(s2,s1)
    except:
        break

发表于 2023-03-19 21:39:44 回复(0)

Python3

言旭

str1,str2 = input() ,input() 
total_list = []
if len(str1)>len(str2):
    str1,str2 = str2,str1
for i in range(len(str1)):
    for j in range(len(str1)):
        if j+i+1<len(str1):
            if str1[i:j+i+1] in str2:
                total_list.append(str1[i:j+i+1])
print(max(total_list,key=len))

使用迭代思想对a进行切片，将包含在b中的所有切片放入一个列表，最后取出列表中长度最长的元素

发表于 2023-03-16 21:53:45 回复(0)

Python3

在做的机考肯定是必过呀

#动态规划解题
def solution(a,b):
    dp = [[0 for i in range(len(a)+1)] for j in range(len(b)+1)]
    l_max = 0
    for i in range(1,len(b)+1):
        for j in range(1,len(a)+1):
            if b[i-1] == a[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            if dp[i][j] > l_max :
                l_max = dp[i][j]
    #用于找出第一个出现的最长字串，必须在短串中找，所以得确定a,b的长短
    for i in range(1,len(a)+1):
        for j in range(1,len(b)+1):
            if dp[j][i] == l_max:
                print(a[i-l_max:i])#注意dp中的i、j对应上字符时始终大1
                return

a,b= input(),input()
#用于保证传入的参数，始终为短串在前、长串在后
temp = a
a = a if len(b)>len(a) else b
b = temp if len(temp)>len(b) else b
solution(a,b)

发表于 2023-02-28 17:21:59 回复(0)

Python3

丶魇

第二个for这里忘记 -i了卡半天

while True:
    try:
        arr1 = input()
        arr2 = input()
        short, long = '', ''
        if len(arr1) < len(arr2):
            short = arr1
            long = arr2
        else:
            long = arr1
            short = arr2
        if short in long:
            print(short)
        else:
            for i in range(len(short)-1, 0, -1):
                for j in range(0, len(short)-i):
                    arr = short[j:j + i + 1]
                    if arr != '' and arr in long:
                        print(arr)
                        break
                    else:
                        continue
                else:
                    continue
                break
    except:
        break

发表于 2023-02-23 16:39:02 回复(0)

Python3

我想吃饭呜呜呜

a,b = input(),input()
if len(a)<len(b):
    a,b = b,a

f = True
for i in range(len(b)-1,0,-1):
    if not f:
        break
    for j in range(0,len(b)-i+1):
        if b[j:j+i] in a:
            print(b[j:j+i])
            f =  False
            break

发表于 2023-02-22 14:49:16 回复(0)

Python3

不会唱搁浅

s1, s2 = input(), input()

s0 = ""

list1, list2 = [], []

if len(s1) > len(s2):

s0 = s1

s1 = s2

s2 = s0

for i in range(len(s1)):

for j in range(i + 1, len(s1) + 1):

if s1[i:j] in s2:

list1.append(s1[i:j])

list1 = sorted(list1, key=lambda x: len(x))

for i in list1:

if len(i) == len(list1[-1]):

list2.append(i)

for i in list2:

if i in s1:

print(i)

break

发表于 2023-02-14 11:39:13 回复(0)

Python3

yorusimo

H75多加一个输入

import sys

lines=sys.stdin.readlines()
s1,s2=lines[0],lines[1]
n1,n2=len(s1),len(s2)
l_max=0
flag=0

# 判断出更短的字符串
if n1>n2:
    s1,s2=lines[1],lines[0]
    n1,n2=len(s1),len(s2)

# dp[i][j]：切片s1[i:j]是否为s2的子串  0：否 1：是
dp=[[0]*n1 for _ in range(n1-1)]
for i in range(n1-1):
    for j in range(i+1,n1):
        if s1[i:j] in s2:
            dp[i][j]=1    
# 最长公共子串长度
for i in range(n1-1):
    for j in range(n1-1,i-1,-1):
        if dp[i][j]==1:
            if j-i>=l_max:
                l_max=j-i
                break
# 输出
for i in range(n1-1):
    for j in range(n1-1,i-1,-1):
        if dp[i][j]==1 and j-i==l_max:
                print(s1[i:j])
                flag=1
                break
    if flag==1:
        break

发表于 2023-02-05 17:22:26 回复(0)

Python3

ax220614

r1,r2 = input(),input()
s1,s2 = [],[]
for i in range(len(r1)):
    for j in range(i+1,len(r1)+1):
        if r1[i:j] in r2:
            s1.append(r1[i:j])                   # 筛选出同时存在于r1和r2中的字串
s2 = []
for i in s1:
    if len(i) == len(sorted(s1,key=len)[-1]):    # 考虑到可能有多个长度相同的‘最长字串’的情况
        s2.append(i)                             # 将可能存在的多个‘最长字串’全部放入s2
s3 = []
if len(r1) > len(r2):
    r1,r2 = r2,r1                                # 设r1为较短的字符串
for i in s2:                                     # 将r1按‘最长字串’进行分割
    s3.append(len(r1.split(i)[0]))               # 分割后得到的第一段序列越短说明‘最长字串’越先出现
index = s3.index(min(s3))                        # 确定较短串中最先出现‘最长字串’的下标
print(s2[index])                                 # 通过下标锁定s2‘最长字串’序列中在较短串中最先出现的那个

发表于 2023-01-26 17:24:31 回复(0)

Python3

在喝茶的咸鱼很温柔

str1 = input()
str2 = input()
if len(str1) < len(str2):
    str1, str2 = str2, str1
dic = {}
for i in range(len(str2)):
    for j in range(i + 1, len(str2) + 1):
        if str2[i:j] in str1:
            dic[str2[i:j]] = j - i
print((sorted(dic.items(), key=lambda x: x[1], reverse=True))[0][0])

发表于 2022-12-14 11:17:32 回复(0)

Python3

牛客266728579号

s1, s2 = input(), input()
length = min(len(s1), len(s2))
if length == len(s2):
    s1, s2 = s2, s1

def f(s1, s2):
    for i in range(length,0,-1):
        for j in range(0,length-i+1):
            if s1[j:j+i] in s2:
                return s1[j:j+i]
    
print(f(s1,s2))

发表于 2022-11-30 16:03:39 回复(0)

Python3

牛友2022

a, b = input(), input()
if len(a) > len(b):
    a, b = b, a

n = 0
for i in range(len(a)):
    sub = a[i-n:i+1]
    if sub in b:
        res = sub
        n += 1
print(res)

发表于 2022-11-22 18:55:21 回复(0)