9
Für die zwei String-Suchalgorithmen: KMP und Suffixbaum, was ist in welchen Fällen vorzuziehen? Geben Sie einige praktische Beispiele.String-Suchalgorithmen
A
Antwort
11
Ein Suffixbaum ist besser, wenn Sie viele Fragen beantworten müssen, wie "Ist die Nadel im Heuhaufen?". KMP ist besser, wenn Sie nur eine Zeichenfolge in einer anderen einzelnen Zeichenfolge suchen müssen und dies nicht oft machen müssen.
Ein Suffixbaum ist eine viel allgemeinere Datenstruktur, so dass Sie viel mehr damit tun können. Sehen Sie, was Sie damit tun können here. KMP ist nützlich, um zu ermitteln, ob eine Zeichenfolge eine Teilzeichenfolge in einer anderen Zeichenfolge ist.
Sie können auch andere Algorithmen wie Boyer-Moore, Rabin-Karp und sogar den naiven Algorithmus ausprobieren, da es Situationen (Eingaben) gibt, in denen eine besser ist als die anderen.
Unterm Strich ist:
- Wenn Sie viele Anfragen wie das habe ich oben erwähnt, ist es lohnt sich, einen Suffix-Baum zu bauen und dann schneller jede Abfrage beantworten.
- Wenn Sie mehr als diese Art von Abfragen ausführen müssen, ist auch ein Suffixbaum zu erstellen.
- Wenn Sie nur gelegentlich feststellen möchten, ob eine Zeichenfolge eine Teilzeichenfolge einer anderen Zeichenfolge ist, verwenden Sie KMP.
Was denken Sie selbst? Jetzt sieht es so aus, als hättest du einen Teil deiner Hausaufgabe kopiert. –
Hausaufgaben? Bitte tag ist so. – DVK
Das sind keine Hausaufgaben. Ich bin ein professioneller Programmierer, der in einer Firma arbeitet. Diese Frage dient nur dazu, Wissen zu erlangen. – avd