最大公共子串

[编程题]最大公共子串

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

给定两个字符串，请编写代码，输出最长公共子串（Longest Common Substring），是指两个字符串中的最长的公共子串，要求子串一定是连续。

数据范围：输入的两个字符串长度满足 $1 \le n \le 100 \$

输入描述:

文本格式，2个非空字符串（字母数字组成），2个字符串以","英文逗号分割。

输出描述:

整形，为匹配到的最长子串长度

示例1

输入

bab,caba

输出

算法知识视频讲解

Python

小小cx猿

s1, s2 = input().split(',')
L1 = len(s1)
L2 = len(s2)
ans = 0
dp = [[0] * (L2 + 1) for _ in range(L1 + 1)]
for i in range(L1):
for j in range(L2):
if(s1[i] == s2[j]):
dp[i+1][j+1] = dp[i][j] + 1
ans = max(ans, dp[i+1][j+1])
print(ans)

发表于 2019-09-20 19:49:51 回复(0)

Python

雷凌云

# 伪DP算法
s1,s2 = input().split(',')
if len(s1) < len(s2):       # 保证长串是 s1
    s1,s2 = s2,s1
dp = 0                      # 最大公共子串的长度
for i in range(len(s1)):
    if s1[i-dp:i+1] in s2:
        dp += 1
print(dp)

发表于 2019-08-21 22:53:07 回复(0)