Exercise 2.2: Longest common substring


Write a function that takes two sequences and returns the longest common substring. A substring is a contiguous portion of a string. For example:

Substrings of ATGCATAT:

TGCA
T
TAT

Not substrings of ATGCATAT:

AGCA              # Skipped T
CCATA             # Added another C
Hello, world.     # Has nothing to do with the input sequence

There may be more than one longest common substring; you only need to return one of them.

The call signature of the function should be

longest_common_substring(s1, s2)

Here are some return values you should get.

Function call

Result

longest_common_substring('ATGC', 'ATGCA')

'ATGC'

longest_common_substring('GATGCCATGCA', 'ATGCC')

'ATGCC'

longest_common_substring('ACGTGGAAAGCCA', 'GTACACACGTTTTGAGAGACAC')

'ACGT'