Das "Shortest Common Superstring"-Problem (SCS) ist ein kombinatorisches Optimierungsproblem, das darin besteht, die kürzeste mögliche Zeichenkette zu finden, die jede Zeichenkette in einer gegebenen Menge als Teilzeichenkette enthält. Das SCS-Problem ist NP-vollständig,[1] daher sind Approximationsalgorithmen von Interesse.
Beispiel: Für die Teilzeichenketten ["AB", "AC", "BA", "BC", "CA", "CB"] lautet ein möglicher SCS "ABACBCA".
Ein bekannter Approximationsalgorithmus ist der Greedy-Algorithmus, der wiederholt zwei Zeichenketten mit maximaler Überlappung zusammenfügt, bis eine einzige Zeichenkette übrig bleibt.[2]
Ein wichtiges Anwendungsgebiet des SCS findet sich bei der Genomanalyse: Aus einer großen Anzahl einzelner sequenzierter DNA-Bruchstücke lässt sich die Gesamtsequenz mittels des SCS ermitteln.