Find the longest common substring from two sentences

Question

My question is how to find the longest common substring from two sentences. For example:

sequence 1 = "there were a dozen eggs in the basket"

sentence 2 = "mike ate a dozen eggs for breakfast"

The longest common substring from sentence 1 and sentence 2 would be "e a dozen eggs ", including the spaces.

My general idea is to create a concatenated string from sentence 1 and sentence 2, separating each sentence with a unique character such as "$" or "#", and then create a suffix tree from these sentences; however, I am not sure how to approach from here.

Answer 1

The longest common substring from two sentences

Using two loops and list comprehension.

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)

Output:

'e a dozen eggs '