首页 > 试题广场 >

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

[编程题]查找两个字符串a,b中的最长公共子串
  • 热度指数：196171 时间限制：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 300、仅由小写字母组成的字符串 s。
\hspace{15pt}第二行输入一个长度为 1 \leqq {\rm len}(t) \leqq 300、仅由小写字母组成的字符串 t。


输出描述:
\hspace{15pt}输出一个字符串，代表 s 和 t 的最长公共子串。如果存在多个答案，输出在较短串中最先出现的那个。
示例1

输入

awaabb
aawbb

输出

aa

说明

\hspace{15pt}在这个样例中，\texttt{ 和 \texttt{ 都是 s 和 t 的最长公共子串，但 \texttt{ 在较短串 s 中首先出现，因此输出 \texttt{。
示例2

输入

abcdefghijklmnop
abcsafjklmnopqrstuvw

输出

jklmnop
算法知识视频讲解
添加回答
Python
牛客590711274号头像 牛客590711274号 
while True:
    try:
        str1=input()
        str2=input() #读取输入
        if len(str1) < len(str2): #以str2 <str1 为前提编写，如果str2 >str1 则换位
            str1,str2 = str2,str1
        size = len(str2) #读取较小字符串长度（永远是str2）
        exit = False#终止loop重设
        for i in range (len(str2)): #每次size从大到小逐渐-1
            for ii in range (len(str2)-size+1): #移动size大小的方块
                n = str1.find(str2[ii:(size+ii)]) #以步长为一遍历size大小方块找寻相同项
                if n != -1:#找到相同
                    print(str2[ii:(size+ii)])
                    exit = True#用于跳出大循环
                    break#跳出本循环
            size = size -1#size减小
            if exit == True:
                break#跳出大循环
    except:
        break

发表于 2021-06-30 13:26:41 回复(0)
Python
牛客诶谁头像 牛客诶谁 
import sys


def dp_func(short_str, long_str):
    dp = [[0 for i in range(len(long_str)+1)] for j in range(len(short_str)+1)]
    # dp[i][j] = d[i-1][j-1] + 1
    mmax = 0
    start = 0

    for i in range(1, len(short_str)+1):
        for j in range(1, len(long_str)+1):
            if short_str[i-1] == long_str[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > mmax:
                    mmax = dp[i][j]
                    start = i - mmax
    return short_str[start:mmax+start]

'''
s1 = input()
s2 = input()
if len(s1) < len(s2):
    print(dp_func(s1, s2))
else:
    print(dp_func(s2, s1))
'''
while True:
    try:
        s1 = input()
        s2 = input()
        if len(s1) < len(s2):
            print(dp_func(s1, s2))
        else:
            print(dp_func(s2, s1))
    except:
        break

# 方法2： 
def func(s1, s2):
    start = 0
    max_len = 0

    for i in range(len(s1)):
        if s1[i] in s2:
            # 注意，j可以从i+max_len+1开始
            for j in range(i+max_len+1, len(s1)+1):
                if s1[i:j] in s2:
                    start = i
                    max_len = j-i
                else:
                    break
    return s1[start:max_len+start]

while True:
    try:
        s1 = input()
        s2 = input()

        # 让s1为较短的字符串
        if len(s1) > len(s2):
            s1, s2 = s2, s1

        print(func(s1, s2))
    except:
        break


编辑于 2021-06-30 19:51:58 回复(0)
Python
二年三班的牛客头像 二年三班的牛客 
while True:
    try:
        str1 = input()
        str2 = input()
        if len(str1) <= len(str2):
            short = str1
            long = str2
        else:
            short = str2
            long = str1
        mutual = ''
        for left in range(len(short)):
            for right in range(left + 1, len(short) + 1):
                    if (short[left:right]) in long:
                        if len(short[left:right]) > len(mutual):
                            mutual = short[left:right]
        print(mutual)
    except EOFError:
        break

发表于 2021-03-27 23:39:21 回复(0)
Python
阿飘030头像 阿飘030 
while True:
    try:
        a=input()
        b=input()
        if len(a)>len(b): #以较短的字符串为目标
            a,b=b,a
        ans=''
        for i in range(len(a)):#在较短的字符串中循环
            j=i+1
            while int(j)<len(a)+1 :
                if a[i:j] in b and len(a[i:j])>len(ans):#找出最长的从i到j的字符串
                    ans=a[i:j] #更新最长的字符串为ans
                j+=1
        print(ans)
    except:
        break

发表于 2020-12-22 10:30:13 回复(0)
Python
大溪地渔民头像 大溪地渔民
动态规划，dp[i][j] 表示以较短字符串的 i 位和较长字符串的 j 位为公共子串的最大长度 
while True:
    try:
        a, b = input(), input()
        a, b = (a, b) if len(a)<=len(b) else (b, a)
        dp = []
        for i in range(len(a)+1):
            dp.append([0] * (len(b)+1))
        longest, r_index = 0, 0
        for i in range(1, len(a)+1):
            for j in range(1, len(b)+1):
                if a[i-1] == b[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    if dp[i][j] > longest:
                        longest = dp[i][j]
                        r_index = i
        print(a[r_index-longest:r_index])
    except:
        break
                   


发表于 2020-12-17 23:07:14 回复(0)
Python
乐观的lishan头像 乐观的lishan 
# 2020年11月17日15:12:44
while True:
    try:
        str1 = input()
        str2 = input()
#       确定短字符串和长字符串，以及短字符串长度
        len1, len2 = map(len, [str1, str2])
        if len1<len2:
            short_str = str1
            long_str = str2
            min_len = len1
        else:
            short_str = str2
            long_str = str1
            min_len = len2
#       从短字符串的长度开始递减搜索公共子串,stop为停止搜索标志位
        length = min_len
        stop = 0
        while length>0:
            for i in range(min_len-length+1):
                if long_str.find(short_str[i:i+length]) != -1:
                    print(short_str[i:i+length])
                    stop = 1
                    break
            if stop==1:
                break
            else:
                length -= 1
    except:
        break
        

发表于 2020-11-17 15:37:28 回复(0)
Python
软弱的我头像 软弱的我 
while True:
    try:
        a, b = input(), input()
        if len(a)>len(b):
            a,b = b, a
        for i in range(len(a),0,-1):
            for j in range(len(a)-i+1):
                if a[j:j+i] in b:
                    print(a[j:j+i])
                    break
            else:
                continue
            break
    except:
        break

发表于 2020-11-06 18:58:07 回复(0)
Python
牛客778193208号头像 牛客778193208号
【永远忘不掉把，因为昨晚20200428华为的机试题，现在折腾出了答案，有点繁琐】
需要注意两点：
（1）因为有重复测试，所以需要添加
while True:
    try:
（2）如何求解列表中的最长元素：max(arr,key=len)
（3）真实做题环境，至少我还是需要借助IDE来辅助循环。


发表于 2020-04-29 09:37:57 回复(1)
Python
牛客454249073号头像 牛客454249073号 
while True:
    try:
        s1 = input()
        s2 = input()
        lenth = 0
        s_list = []
        if len(s1)>len(s2):
            s1, s2 = s2, s1
        for i in range(len(s1)):
            for j in range(i+1, len(s1)+1):
                temp = s1[i:j]
                if temp in s2 and j-i>lenth:
                    s_list.append(temp)
                    lenth = j-i
        print(s_list[-1])
    except:
        break

发表于 2020-03-29 00:44:03 回复(0)
Python
谢小橙头像 谢小橙 
def longest_public_str(str1,str2):
    if len(str1)>len(str2):
        long_str=str1
        short_str=str2
    else:
        long_str=str2
        short_str=str1
    
    # l 初始化
    l=[]
    for k in range(len(short_str)):
        if short_str[k] in long_str:
            l.append(short_str[k])
            break
    # l=['a']
    
    # 最长子串长度至少为2
    for i in range(len(short_str)):
        s=''
        s+=short_str[i]
        for j in range(i+1,len(short_str)):
            s+=short_str[j]
            if s in long_str and len(s)>len(l[0]):
                l.pop()
                l.append(s)
    return l[0]

while True:
    try:
        str1=input()
        str2=input()
        print(longest_public_str(str1,str2))
    except:
        break

发表于 2020-02-19 21:40:33 回复(0)
Python
牛客962313693号头像 牛客962313693号 
while True:
    try:
        a_l = input()
        b_l = input()
        max_l =''
        min_l =''
        if len(a_l)>=len(b_l):
            max_l = a_l
            min_l = b_l
        else:
            max_l = b_l
            min_l = a_l
        n = len(min_l)
        outs =''
        while n > 0:
            if n == len(min_l) and min_l in max_l:
                outs =min_l
                break
            else:
                for i in range(len(min_l)):
                    #一开始少了一个判断导致超过字符串长度会出现1个字符
                    if (i+n)<len(min_l):
                        x = min_l[i:i+n]
                        if x in max_l:
                            outs = x
                            break
            if outs!='':
                break
            else:
                n -= 1
        print(outs)
    except:
        break
题目不难，调试半天，一直以为我退出循环的地方错了，后来发现，当i+n超过 最大长度，会输出1-2个字符的片段，提前匹配上，很尴尬
发表于 2019-12-21 01:30:13 回复(0)
Python
过过过bei头像 过过过bei
多半python通过的代码都是不完整的，没有考虑异常什么的错误答案太多了，因此贴上本人代码
while True:
    try:
        a = input()
        b = input()
        n = 0
        s = ''
        if len(a) >= len(b):
            a,b = a, b
        for i in range(len(a)+1):
            if a[i-n:i+1] in b:
                if len(a[i-n:i+1]) == len(s):
                    #make sure 若有多个，输出在较短串中最先出现的那个
                    pass
                else:
                    s = a[i-n:i+1]
                n += 1
        print(s)
    except:
        break
发表于 2019-10-03 22:25:15 回复(3)
Python
秋意浓201903221653622头像 秋意浓201903221653622 
while True:
    try:
        s1 = input()
        s2 = input()

        short, long = (s1, s2) if len(s1) < len(s2) else (s2, s1)

        repeat = ''

        for i in range(len(short)):
            for j in range(len(short)):
                if short[i:j + 1] in long and j + 1 - i > len(repeat):
                    repeat = short[i:j + 1]
        print(repeat)
    except:
        break

发表于 2019-08-28 15:18:15 回复(0)
Python
cyd1310997头像 cyd1310997 
import re
while True:
    try:
        a, b = input(), input()
        if len(a) > len(b): a, b = b, a
        c = a + '\n' + b
        L = [re.search(r'(.+)(?=.*\n.*\1)', c[i:]) for i in range(len(a))]
        L = [i.group() for i in L if i]
        print(max(L, key = len))
    except: break

编辑于 2019-08-19 14:18:15 回复(3)
Python
lx的流星头像 lx的流星 
while True:
    try:
        n1=input().strip()
        n2=input().strip()
        list1=[]
        lenth1=len(n1)
        lenth2=len(n2)
        min_lenth=min(lenth1,lenth2)
        len1=0
        result=''
        if lenth1>=lenth2:
            n1,n2=n2,n1
        for i in range(min_lenth,1,-1):
            for j in range(min_lenth-i+1):
                n1_1=n1[j:j+i]
                if n2.find(n1_1)>=0:
                    if i>len1:
                        len1=i
                        result=n1_1
        print(result)
    except:
        break

长见识了

发表于 2019-06-26 14:26:15 回复(0)
Python
夜深沉1325头像 夜深沉1325 
while 1:
    try:
        c = input()
        d = input()
        if len(c) <= len(d):
            a,b = c,d
        else:
            a,b = d,c
        res = ""
        for i in range(len(a),0,-1):
            if res == "":
                for j in range(0,len(a)-i + 1):
                    s = a[j:i+j]
                    if s in b:
                        res = s
                        print(res)
                        break
            else:
                break
    except:
        break
发表于 2019-03-31 20:01:35 回复(0)
Python
CassielLee头像 CassielLee 
/*矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况，若是匹配则为1,否则为0*/
def getLCS(string1 , string2):
    matrix = [[0 for i in range(len(string2)+1)]  for j in range(len(string1)+1)]
    maxl = 0
    p = 0
    for n in range(len(string1)):
        for m in range(len(string2)):
            if string1[n] == string2[m]:
                matrix[n+1][m+1] = matrix[n][m] + 1
                if matrix[n+1][m+1] > maxl:
                    maxl = matrix[n+1][m+1]
                    p = n + 1
    return string1[p-maxl:p]

while True:
    try:
        string1 = input()
        string2 = input()
        print(getLCS(string2,string1))
    except:
        break

发表于 2018-09-01 19:45:40 回复(0)
提交观点

问题信息

字符串
难度：
18条回答 63951浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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