首页 > 试题广场 >

公共子串计算

[编程题]公共子串计算

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

给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。

注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。

数据范围：字符串长度： $1\le s\le 150\$

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

输入描述:

输入两个只包含小写字母的字符串

输出描述:

输出一个整数，代表最大公共子串的长度

示例1

输入

asdfas
werasdfaswer

输出

算法知识视频讲解

Python

二年三班的牛客

str1 = input()
str2 = input()
mutual = ''
for left in range(len(str1)):
    for right in range(1, len(str1) + 1):
            if str2.count(str1[left:right]) > 0:
                if len(str1[left:right]) > len(mutual):
                    mutual = str1[left:right]
print(len(mutual))

发表于 2021-03-27 22:57:59 回复(0)

Python

星凌九天

while True:
try:
list1=list(input())
list2=list(input())
list3=[]
m=0
n=0
k=len(list1)
w=len(list2)
if k>w:
list3=list2
list2=list1
list1=list3
y=k
k=w
w=y
for i in range(k):
for j in range(w):
if list1[i] == list2[j]:
n=1
o=min(k-i,w-j)
for r in range(i+1,i+o):
if list1[r]==list2[r+j-i]:
n+=1
m=n if n>m else m
else:
break
print(m)
except:
break

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

Python

牛客760726790号

while True:
try:
a = input()
b = input()

m,n = len(a),len(b)

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

max_len = 0

for i in range(1,m+1):
for j in range(1,n+1):
if a[i-1] == b[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
if dp[i][j] > max_len:
max_len = dp[i][j]
print(max_len)
except:
break

发表于 2021-03-06 01:07:49 回复(0)

Python

Willfu

while True:
    try:
        a = input()
        b = input()
        if len(a) > len(b):
            a, b = b, a
        max_len = 0
        i = 0
        li = []
        for i in range(len(a)):
            for j in range(len(a)):
                if i <= j and a[i:j] in b:
                    li.append(j-i)

        print(max(li))
    except:
        break

暴力枚举，简单粗暴

发表于 2021-02-27 14:37:11 回复(0)

Python

牛客44738297号

O（n）复杂度，python

while True:
    try:
        a = input()
        b = input()
        if len(a) > len(b):
            a,b = b,a
        max_length = 0
        i = 0
        while i + max_length < len(a):
            while a[i:i + max_length + 1] in b:
                max_length += 1
            i += 1
        print(max_length)
    except:
        break

发表于 2021-02-21 17:52:29 回复(0)

Python

牛客692693699号

while True:
    try:
        a = input()
        b = input()
        num = 0
        for i in range(len(a)):
            if a[i-num: i+1] in b:
                num += 1
        print(num)
    except:
        break

编辑于 2021-02-17 15:38:06 回复(1)

Python

牛客227574939号

动态规划才是这个题的考点和正确解决办法，我们先看下题目，两个字符串中最大公共子串的长度，即找出最大公共子串。光看示例这个案例是远远不够的，如果这两个字符串特别长，且不知道最长的子串是在中间，还是在末尾，还是有两个相同的子串，怎么办？列出了用例，题就好解了

def find_max_substr(A,B):
    n, m = len(A), len(B)
    dp = [[''] * (m + 1) for _ in range(n + 1)]
    ans = ''
    for i in range(n - 1, -1, -1):
        for j in range(m - 1, -1, -1):
            dp[i][j] = dp[i + 1][j + 1] + B[j] if A[i] == B[j] else ''
            if len(dp[i][j]) > len(ans):
                ans = dp[i][j]
#     print('最长公子串为：',ans[::-1])
    return len(ans)

str1 = str(input())
str2 = str(input())
print(find_max_substr(str1,str2))

发表于 2021-01-22 17:58:00 回复(0)

Python

大溪地渔民

思路：dp[i][j] 表示以 a[i], b[j] 为结尾的最大子串长度，则 dp[i][j] == dp[i-1][j-1] + 1 if a[i] == b[j] else 0

def cal(a, b):
    a, b = " "+a, " "+b
    dp = [
        [0 for _ in b] for _ in a
    ]
    max_len = 0
    for i in range(1, len(a)):
        for j in range(1, len(b)):
            if a[i] == b[j]:
                dp[i][j] = dp[i-1][j-1] + 1
                max_len = max([max_len, dp[i][j]])
    return max_len


a, b = input(), input()
print(cal(a, b))

发表于 2020-12-13 00:09:37 回复(0)

Python

纪铭

s0 = input()
s1 = input()
a = 0
for i in range(len(s0)):
for j in range(len(s0)):
if s0[i:a+i+1] in s1 and a<len(s0[i:a+i+1]):
a =len(s0[i:a+i+1])
else:
break
print(a)

编辑于 2020-11-29 21:09:51 回复(0)

Python

乐观的lishan

# 2020年11月14日17:08:54
while True:
    try:
        str1 = input().lower()
        str2 = input().lower()
#       寻找长字符串、和短字符串
        if len(str1) > len(str2):
            short_str, long_str = str2, str1
        else:
            short_str, long_str = str1, str2
#       初始最大公共字符串长度为输入的短字符串长度
        length_max = len(short_str)
        find = 0
#       从最大值开始匹配，逐渐减少字符串长度
        while length_max > 0:
            for i in range(len(short_str)-length_max+1):
                sub_str = short_str[i:i+length_max]
#               子字符串也在长字符串中
                if sub_str in long_str:
                    find = 1
                    break
            if find == 1:
                break
            length_max -= 1
        print(length_max)
    except:
        break

发表于 2020-11-14 17:47:25 回复(0)

Python

destpaci

使用较短字符串长度倒序遍历，取下标时在纸上推导很容易理解，exit()退出程序

a = input().lower()
b = input().lower()
maxlen = min(len(a),len(b))
for i in range(maxlen,0,-1):
    for p in range(0,len(a)-i+1):
        for q in range(0,len(b)-i+1):
            if a[p:p+i] == b[q:q+i]:
                print(i)
                exit()

发表于 2020-10-13 16:45:37 回复(0)

Python

牛客luckylulu

使用动态规划进行求解。

如 w e r a s d f a s

a 0 0 0 1 0 0 0 1 0

s 0 0 0 0 2 0 0 0 2

d 0 0 0 0 0 3 0 0 0

f 0 0 0 0 0 0 4 0 0

a 0 0 0 1 0 0 0 5 0

s 0 0 0 0 2 0 0 0 6

根据给出的字符串生成二维矩阵，核心代码如下：


if str1[i] == str2[j]:     # 如果字符相等
   dp[i][j] = dp[i-1][j-1] + 1    # 则在对角线上的上一个dp值加一
else:
   dp[i][j] = 0

最后结果求的是dp矩阵里的max。

全部代码

# 动态规划
# 最大公共子串的长度·
str1 = input()
str2 = input()
# 定义初始二维数组
# 以第一个字符串为列，以第二个字符串为行
# 加 1 是为了保证动态规划第一步的前一个状态为0
dp = [[0]*(len(str2)+1) for i in range(len(str1)+1)]
# print(res)
for i in range(1, len(str1)+1):
    for j in range(1, len(str2)+1):
        if str1[i-1] == str2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = 0

# print(dp)
# 输出dp里的最大值
res = []
for i in dp:
    if res == []:
        res.append(max(i))
    if max(i)>res[-1]:
        res.pop()
        res.append( max(i))
    else:
        continue
print(res[-1])

编辑于 2020-09-23 13:41:58 回复(0)

Python

牛客902100313号

while True:
try:
str1 = input()
str2 = input()
list1 = list(str1)
list2 = list(str2)
len1 = len(str1)
len2 = len(str2)
len3 = min(len1,len2)
count = 0
if len3 == len1:
list3 = list1
str3 = str2
elif len3 == len2:
list3 = list2
str3 = str1
for i in range(1,len3):
for j in range(0,len3-i+1):
list4 = []
for x in range(j,j+i):
list4.append(list3[x])
str4 = ''.join(list4)
if str4 in str3:
count = max(count,i)
print(count)
except:
break

发表于 2020-09-09 03:17:00 回复(0)

Python

JaquesJames

while True:
    try:
        a = str(input())
        b = str(input())
        n = 0
        for i in range(len(a)):
            if a[i-n:i+1] in b:
                n += 1
        print(n)
    except:
        break

发表于 2020-08-23 16:33:59 回复(0)

Python

业余小菜鸟

def number(str_short,str_long): 
    res = 0
    for i in range(len(str_short)):
        for j in range(len(str_short),i-1,-1):
            if str_short[i:j] in str_long:
                if len(str_short[i:j]) > res:
                    res = len(str_short[i:j])
                break #找到i开始最长的子串
    return res
while True:
    try:
        str_short = input().lower()
        str_long = input().lower()
        #交换一下
        if len(str_short) > len(str_long):
            str_short,str_long = str_long,str_short
        print(number(str_short,str_long)) 
    except:
        break

发表于 2020-08-07 11:14:48 回复(0)

Python

gu_xing

双指针解法：

def get_maxlength(a,b):
    if len(a) > len(b):
        a, b = b, a
        
    start = 0
    long = 0
    for i in range(1, len(a) + 1):
        if a[start:i] in b:
            long = max(long, i-start)
            continue
        start += 1
    return long
        
        
while True:
    try:
        a, b = input(), input()
        print(get_maxlength(a, b))
        
    except:
        break

发表于 2020-08-04 11:39:30 回复(0)