Find the Longest Substring Shared by Two Strings solved by 306

In “Find the Longest Repeat in a String”, we encountered the Longest Repeat Problem, which could be solved using a suffix tree.

The second additional exercise that we will consider is below.

Longest Shared Substring Problem

Find the longest substring shared by two strings.

Given: Strings Text₁ and Text₂.

Return: The longest substring that occurs in both Text₁ and Text₂. (Multiple solutions may exist, in which case you may return any one.)

Sample Dataset

TCGGTAGATTGCGCCCACTC
AGGGGCTCGCAGTGTAAGAA

Sample Output

AGA

Extra Datasets

Click for debug datasets