Het probleem van de kortste superstring (shortest superstring problem, of SSP) krijgt als input een collectie van string en probeert een string S te vinden die alle gegeven strings als substring bevat, zodanig dat de lengte van S zo klein mogelijk is.

Bv. de verzameling strings {000, 001, 010, 011, 100, 101, 110, 111} heeft als kortste superstring 0001110100.

Een gretige strategie, die een benadering voor de kortste superstring levert, bestaat erin om herhaaldelijk een paar substrings met maximale overlap samen te voegen, totdat uiteindelijk een enkele string overblijft. De overlap van een string p met een string q is gedefinieerd als de lengte van de langste prefix van q die overeenstemt met een suffix van p. Als twee paren (p1,q1) en (p2,q2) dezelfde overlap hebben, dan kiezen we het paar met de lexicografisch kleinste p.

Opgave

Schrijf een Python functie overlap die twee strings p en q als parameter krijgt en die de overlap van p met q teruggeeft.

Schrijf een Python functie greedySSP die een verzameling strings als parameter neemt en die een superstring teruggeeft die bekomen werd met bovenstaande gretige strategie.

Voorbeeld

>>> overlap('AATGGATGGAT', 'GGATTCTTGA')
4
>>> greedySSP(['AAT', 'TTAAAA'])
'TTAAAAT'