Find the Shortest Non-Shared Substring of Two Strings solved by 254

In “Find the Longest Repeat in a String” and “Find the Longest Substring Shared by Two Strings”, we encountered two problems that could be solved using a suffix tree. A third such problem is shown below.

Shortest Non-Shared Substring Problem

Find the shortest substring of one string that does not appear in another string.

Given: Strings Text₁ and Text₂.

Return: The shortest substring of Text₁ that does not appear in Text₂. (Multiple solutions may exist, in which case you may return any one.)

Sample Dataset

CCAAGCTGCTAGAGG
CATGCTGGGCTGGCT

Sample Output

AA

Extra Datasets

Click for debug datasets