Dati alcuni frammenti di stringhe, vorrei trovare la stringa singola più breve possibile ("stringa di output") che contenga tutti i frammenti. I frammenti possono sovrapporsi l'un l'altro nella stringa di output.
Esempio:
Per i frammenti di stringhe:
BCDA
AGF
ABC
La seguente stringa di output contiene tutti i frammenti ed è stata creata dall'appendice naive:
BCDAAGFABC
Tuttavia questa stringa di output è migliore (più breve), poiché utilizza sovrapposizioni:
ABCDAGF
^
ABC
^
BCDA
^
AGF
Sto cercando algoritmi per questo problema. Non è assolutamente importante trovare la stringa di uscita strettamente più breve, ma più breve è, meglio è. Sto cercando un algoritmo migliore di quello ovvio e ovvio che tenterebbe di aggiungere tutte le permutazioni dei frammenti di input e rimuovere le sovrapposizioni (che sembrerebbe essere NP-Completo).
Ho iniziato a lavorare su una soluzione e si sta dimostrando piuttosto interessante; Mi piacerebbe vedere cosa potrebbero venire in mente altre persone. Aggiungerò il mio work-in-progress a questa domanda tra poco.