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

Question

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

序列1=“篮子里有一打鸡蛋”

第2句=“迈克早餐吃了一打鸡蛋”

第一句和第二句中最长的常见子串是“一打鸡蛋"，包括空格。

我的一般想法是从第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 '