从两个句子中找出最长的公共子串

Question

我的问题是如何从两个句子中找到最长的公共子字符串。例如：

序列1＝"；篮子里有十几个鸡蛋；

句子2＝"；迈克早餐吃了一打鸡蛋；

来自句子1和句子2的最长公共子串将是"0"；e一打鸡蛋"；，包括空间。

我的总体想法是从句子1和句子2创建一个连接字符串，用一个独特的字符(如"(分隔每个句子$"或"#&"；，然后根据这些句子创建一个后缀树；然而，我不知道如何从这里着手。

Answer 1

两个句子中最长的公共子字符串

使用两个循环和列出理解。

s1 = "there were a dozen eggs in the basket"
s2 = "mike ate a dozen eggs for breakfast"
lst=[s1[i:j] for i in range(len(s1)) for j in range(len(s1)) if s1[i:j] in s2]
result = max(lst, key = len)
print(result)

输出：

'e a dozen eggs '