Algoritmi di ricerca stringhe

Question

Per i due algoritmi di ricerca stringhe: KMP e albero dei suffissi, che è preferibile in quali casi? Dare alcuni esempi pratici.

Answer 1

Un albero di suffisso è migliore se si deve rispondere a molte domande come "l'ago è presente nel pagliaio?". KMP è migliore se devi cercare una sola stringa in un'altra stringa singola e non doverlo fare molte volte.

Un albero di suffisso è una struttura di dati molto più generale, quindi è possibile fare molto di più con esso. Scopri cosa puoi fare con esso here. KMP è utile per scoprire se una stringa è una sottostringa in un'altra stringa.

Si potrebbe anche voler controllare altri algoritmi, come ad esempio Boyer-Moore, Rabin-Karp e anche l'algoritmo ingenuo, in quanto vi sono situazioni (input) in cui uno è migliore degli altri.

Linea di fondo è:

1. Se avete un sacco di domande come quello che ho citato sopra, vale la pena di costruire un albero di suffissi e poi rispondere a ogni query più velocemente.
2. Se è necessario fare più di questo tipo di query, vale anche la costruzione di un albero di suffisso.
3. Se ci si preoccupa solo occasionalmente di trovare se una stringa è una sottostringa di un'altra stringa, quindi utilizzare KMP.