题解 | #查找两个字符串a,b中的最长公共子串#
查找两个字符串a,b中的最长公共子串
https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506
from operator import itemgetter
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
lst = []
for j in range(len(str_j) - len(str_i) + 1):
maxlen = 0
te_len = 0
pos = 0
for i in range(len(str_i)):
if str_j[j:j + len(str_i)][i] == str_i[i]:
te_len = te_len + 1
if te_len >= maxlen:
maxlen = te_len
pos = i-maxlen+1
else:
te_len = 0
#print(maxlen,pos)
lst.append((maxlen,pos))
#print(sorted(lst,key=itemgetter(0)))
a = sorted(lst,key=itemgetter(0))[-1][0]
zuobiao = sorted(list(filter(lambda x :x[0]==a,lst)),key=itemgetter(1))[0]
#print(zuobiao)
print(str_i[zuobiao[1]:zuobiao[1]+zuobiao[0]])
滑动窗口