Algoritmo per trovare la sottostringa comune tra le stringhe N

Question

Ho familiarità con gli algoritmi LCS per 2 stringhe. Alla ricerca di suggerimenti per la ricerca di sottostringhe comuni in stringhe 2..N. Potrebbero esserci più sottostringhe comuni in ogni coppia. Ci possono essere diverse sottostringhe comuni in sottoinsiemi delle stringhe.

stringhe: (ABCDEFGHIJKL) (DEF) (ABCDEF) (BIJKL) (FGH)

stringhe comuni:

1/2 (DEF) 
1/3 (ABCDEF) 
1/4 (IJKL) 
1/5 (FGH) 
2/3 (DEF) 

stringhe più lunghe comuni:

1/3 (ABCDEF) 

corde più comuni:

1/2/3 (DEF) 

Answer 1

Questo sor t di cose è fatto tutto il tempo nell'analisi della sequenza del DNA. Puoi trovare una varietà di algoritmi per questo. Una raccolta ragionevole è elencata here.

C'è anche l'approccio a forza bruta di fare tabelle di ogni sottostringa (se siete interessati solo a quelle brevi): formano un albero n-ario (N = 26 per le lettere, 256 per ASCII) ad ogni livello e memorizzare gli istogrammi del conteggio su ogni nodo. Se si eliminano nodi poco utilizzati (per mantenere i requisiti di memoria ragionevoli), si finisce con un algoritmo che trova tutte le sottosequenze di lunghezza fino a M in qualcosa come N * M^2 * log (M) tempo per l'input di lunghezza N. Se invece dividi questo in K separate stringhe, puoi costruire la struttura ad albero e solo leggere la/le risposta/e in un singolo passaggio attraverso l'albero.

Answer 2

Gli alberi SUFFIX sono la risposta a meno che non si abbiano stringhe veramente grandi in cui la memoria diventa un problema. Prevedi 10 ~ 30 byte di utilizzo della memoria per carattere nella stringa per una buona implementazione. Ci sono anche un paio di implementazioni open-source, che semplificano il tuo lavoro.

Ci sono anche altri algoritmi di succinta, ma sono più difficili da implementare (cercare "alberi di suffissi compressi").