Gegeven is een verzameling strings \((s_1,...,s_n)\). Een kortste superstring is een string \(s\) die alle strings \(s_1,...,s_n\) als substrings bevat, zodanig dat de lengte van \(s\) zo klein mogelijk is.

Voorbeeld

Gegeven de strings (GTATTG, GATT, AATTGC, ATTGAT, TGCGT, TTGA), dan is de kortste superstring AATTGCGTATTGATT. In dit voorbeeld zijn de strings DNA-sequenties, een veelvoorkomende toepassing van dit probleem in de bioinformatica: DNA wordt doorgaans in sterk overlappende stukjes ingelezen wegens de beperkingen van de huidige apparatuur en vervolgens terug aan elkaar gezet. De kortste superstring vormt dan een benadering voor het originele DNA.

Ontwerp en implementeer een gretig benaderingsalgoritme (polynomiale tijd) voor dit probleem. Doe dit door een methode public String shortest(List<String> strings), die aanwezig is in de gegeven interface Superstring¹, te implementeren in een klasse GreedySuperstring. Deze methode heeft een lijst van strings als input en geeft een benadering voor de kortste superstring terug.

In de interface Superstring is ook een statische methode static int overlap(String str1, String str2) geïmplementeerd die de lengte van de overlap van de twee strings bepaalt. Deze methode kan je gebruiken bij het implementeren van de methode shortest en roep je op als Superstring.overlap(str1, str2).

Gebruik eventueel de testklasse SimpleTest² om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.