The shortest superstring problem (SSP) takes as input a collection of distinct strings and tries to find a string S that contains all given strings as substrings, such that the length of S is as small as possible.

E.g., the set of strings {000, 001, 010, 011, 100, 101, 110, 111} has as shortest superstring 0001110100.

A greedy approach, resulting in an approximation for the shortest superstring, consists in repeatedly merging a pair of substrings with maximum overlap, until one string remains. The overlap of a string p with a string q is defined as the length of the longest prefix of q that matches a suffix of p. If two pairs (p1,q1) and (p2,q2) have the same overlap, then we choose the pair with the lexicographically smallest p.

Assignment

Write a Python function overlap which takes two strings p and q as parameter and which returns the overlap of p with q.

Write a Python function greedySSP which takes a set of strings as parameter and which returns a superstring obtained by the above greedy approach.

Example

>>> overlap('AATGGATGGAT', 'GGATTCTTGA')
4
>>> greedySSP({'AAT', 'TTAAAA'})
'TTAAAAT'