Ho una sequenza di permutazioni formate usando queste stringhe: "A" , "BC" e "D" . Le permutazioni sono:
BCAD
ABCD
BCDA
DABC
ADBC
DBCA
Ora ho bisogno di decodificare questo; Ad esempio, ho un file di testo contenente le sequenze, dovrei essere in grado di dire le stringhe utilizzate per costruire le permutazioni. Quale algoritmo posso usare?
Questo è correlato al problema di sottostringa più comune più comune e può essere risolto utilizzando un Albero dei suffissi generalizzato .
Utilizza l'algoritmo di Ukkonen per Costruisci un albero (non un albero binario), aggiungendo nodi mentre analizzi il file . L'algoritmo di Ukkonen funziona in tempo O (n) (lineare), per alfabeti a dimensione costante e O (n log n) in generale.
I nodi foglia dell'albero possono quindi essere attraversati per ottenere le sequenze originali.
Seguendo il tuo esempio e supponendo che ogni personaggio sia unico, un semplice algoritmo potrebbe essere:
// Grab the first character of each line
// If it hasn't been encountered before, add to a collection
// Examine the first permutation
// Read each character into a string until a match is found in your collection
// Store the found string
// Repeat
Leggi altre domande sui tag algorithms