Algorithmes de recherche de chaîne

Question

Pour les deux algorithmes de recherche de chaîne: KMP et arborescence de suffixes, laquelle est préférée dans quels cas? Donnez quelques exemples pratiques.

Answer 1

Un arbre de suffixe est préférable si vous devez répondre à beaucoup de questions telles que "l'aiguille est-elle présente dans la meule de foin?". KMP est meilleur si vous avez seulement à chercher une chaîne dans une autre seule chaîne, et ne pas avoir à le faire beaucoup de fois. Un arbre de suffixe est une structure de données beaucoup plus générale, vous pouvez donc en faire beaucoup plus avec lui. Voyez ce que vous pouvez en faire here. KMP est utile pour trouver si une chaîne est une sous-chaîne dans une autre chaîne.

Vous pouvez également consulter d'autres algorithmes, tels que Boyer-Moore, Rabin-Karp et même l'algorithme naïf, car il existe des situations (entrées) dans lesquelles l'un est meilleur que les autres.

Bottom line est:

1. Si vous avez beaucoup de questions comme celle je l'ai mentionné ci-dessus, il vaut la peine de construire un arbre suffixe, puis répondre plus rapidement chaque requête.
2. Si vous avez besoin de faire plus que ce type de requêtes, une arborescence de suffixes vaut également la peine d'être créée.
3. Si vous ne vous souciez que de trouver occasionnellement si une chaîne est une sous-chaîne d'une autre chaîne, utilisez KMP.