Algorithmen und Datenstrukturen · Senior · Frage 21 von 75
Was ist die Kernidee der String-Suche nach Rabin-Karp?
- 1Ein Rolling Hash vergleicht das Muster mit jedem Fenster in O(1)
- 2Es springt anhand des letzten Zeichens des Musters weiter
- 3Es baut einen Trie aller Suffixe des Texts
Antwort zeigen
Richtige Antwort: Ein Rolling Hash vergleicht das Muster mit jedem Fenster in O(1)
Erklärung
Rutscht das Fenster um ein Zeichen, wird der Hash aktualisiert, indem man das alte Zeichen entfernt und das neue hinzufügt. Nur Fenster mit passendem Hash werden Zeichen für Zeichen verglichen. Es glänzt, wenn man viele Muster gleichzeitig sucht.