Dato un elenco di stringhe, trova ogni coppia $ (x, y) $ dove $ x $ è una successiva di $ y $.Possibile fare meglio di $ o (n ^ 2) $?

Question

Considerare il seguente problema algoritmico: dato un elenco di stringhe $ l= [s_1, s_2, \ dots, s_n] $ , vogliamo sapere tutte le coppie < Span Class="Math-Container"> $ (x, y) $ dove $ x $ è una successiva di $ y $ . Possiamo assumere che tutte le stringhe siano di lunghezza alla massima classe $ m $ , dove $ m << n $ e sono tutti su un alfabeto finito $ \ sigma $ con $ | \ Sigma | << N $ . Potremmo anche supporre che il numero di coppie $ (x, y) $ dove $ x $ è a La successiona di $ y $ è molto più piccola di $ n $ .

Un algoritmo banale sarebbe questo:

1. foreach x in L:
2.   foreach y in L:
3.      if x is subsequence of y:
4.         OUTPUT x,y

.

Tuttavia, questo ha complessità $ o (n ^ 2 \ clot m) $ - Sono curioso di sapere se c'è un algoritmo più veloce (più veloce dato che il Numero di coppie $ (x, y) $ è molto più piccola di $ n $ , quindi ad esempio un Algoritmo con complessità a seconda del numero di coppie di uscita).

Si noti che questa domanda è un seguito da Questa domanda , che riguarda lo stesso problema ma per sottostringhe (non successive). Lì, l'algoritmo Aho-Corasick ha risolto il mio problema perfettamente - è lì forse somethign come questo, ma per le successive?

Answer 1

No, non è possibile fare meglio a meno che la forte ipotesi di tempo esponenziale (Seth) non riesca. Se potessimo risolvere questo problema sostanzialmente più veloce di $ o (n ^ 2) $ otterremmo immediatamente un algoritmo molto più veloce per risolvere la soddisfazione del problema completa NP. Questo è vero anche per $ m $ leggermente più di $ \ log (n) $ e il caso in che vogliamo decidere se tale coppia $ (x, y) $ esiste affatto.

Vedi, ad esempio, Queste note di lezione sotto la sezione 3 "Tight Limiti inferiori per i vettori ortogonali ". La dimostrazione è analoga alla prova del teorema 2 in queste note di lezione.

In primo luogo, consideriamo il problema più generale delle due serie di stringhe $ x, y $ , trovando se qualche stringa in $ X $ è una successiva di una stringa in $ y $ .

Dato una formula sat, abbiamo diviso la sua $ N $ variabili in due serie uguali di $ N / 2 $ < / span> variabili. In $ \ Sigma $ Prendiamo un personaggio corrispondente ad ogni clausola. In $ x $ Aggiungiamo una stringa per ogni possibile assegnazione alla prima metà delle variabili, con un personaggio corrispondente ad ogni clausola non soddisfatto da quelle variabili. Nel frattempo, in $ y $ , aggiungiamo una stringa per ogni assegnazione alla seconda metà delle variabili, con un personaggio per ogni clausola che è soddisfatta da quelle variabili. Chiaramente, la formula è soddisfatta se e solo se una certa stringa in $ x $ è una successiva di qualche stringa in $ y $ .

Se questo problema può essere risolto sostanzialmente più veloce di $ o (n ^ 2) $ , quindi fornisce un algoritmo sostanzialmente più veloce per la soddisfattiva della $ 2 ^ N $ . Supponiamo che il problema possa essere risolto in $ o (n ^ {1.99}) $ tempo, allora la soddisfabilità potrebbe essere risolta in $ (2 ^ {n / 2}) ^ {1.99}= o (2 ^ {0.996n}) $ che contraddice Seth.

Nel tuo problema, c'è solo un singolo set di stringhe, tutte possono essere una successiva di a vicenda. Questo non è tuttavia un problema, poiché possiamo semplicemente modificare le stringhe nella nostra istanza in modo tale che nessuna stringa $ y $ è una successiva di qualsiasi altra stringa (ad esempio mediante imbottitura Tutte le stringhe in $ y $ per avere la stessa lunghezza) e imbottitura allo stesso modo ogni stringa in $ x $ alla stessa lunghezza di altre stringhe in $ x $ (ma sostanzialmente più breve delle stringhe in $ y $ ) .

Ciò può probabilmente anche essere fatto con un alfabeto di dimensioni costante (probabile nemmeno binario), ma ciò richiede una codifica più intelligente.