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

while True:
    try:
        s1 = input()
        s2 = input()
        n = 0
        max_sub = ''
        if len(s2)<len(s1):
            s1, s2 = s2, s1
        for i in range(len(s1)):
            if s1[i-n:i+1] in s2:
                max_sub = s1[i-n:i+1]
                n += 1
        print(max_sub)
    except:
        break

# 也是服了，存在多解时例子的答案只有一个就算了，
# 关键还不是第一个找到的（在str1位置靠前的）
# 以下动态规划代码，dp数组直接存储子串
"""
最长公共子串问题动态规划时关键在于状态的定义,比较巧妙
dp[i][j]表示以str1的第i个字符和str2的第j个字符结尾的公共子串。
注意，是以str1第i个字符和str2第j个字符结尾的公共子串，
如果str1第i个字符和str第j个字符不相等，那么不可能存在以它们结尾的公共子串。认为空字符''
那么状态转移方程容易得出：如果str1第i个字符和str第j个字符相等，
那么dp[i][j]就是dp[i-1][j-1]+str1[i-1]，因为多了一个公共字符，
如果str1第i个字符和str第j个字符不相等，那么以它们结尾的公共子串不存在，dp[i][j]=''
"""

def longest_common_substring(str1, str2):
    m = len(str1)
    n = len(str2)
    dp = [[""] * (n + 1) for _ in range(m + 1)]  # 状态直接存储子串
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + str2[j - 1]
    flattened_dp = [item for sublist in dp for item in sublist]
    # flattened_dp.reverse()
    return max(flattened_dp, key=lambda x: len(x))


import sys

lines = []
for line in sys.stdin:
    line = line.strip()
    if line == "":
        break
    lines.append(line)

str1, str2 = lines
print(longest_common_substring(str1, str2))

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)

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)

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)

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)

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])

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中的所有切片放入一个列表，最后取出列表中长度最长的元素

#动态规划解题
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)

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

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