Polynomiales String-Hashing

Oft müssen Sie prüfen, ob zwei Teilzeichenketten gleich sind. Zeichenweise Vergleiche sind langsam, daher wandeln wir jede Zeichenkette in eine Zahl um. 🔢

Ein Hash bildet eine Zeichenkette auf eine einzelne Ganzzahl ab. Wenn sich zwei Zeichenketten unterscheiden, sind auch ihre Hashes fast immer verschieden.

Wir lesen jedes Zeichen als Ziffer zur Basis p. Diese Polynom-Betrachtung verwandelt die Zeichenkette in eine große gewichtete Summe.

Wählen Sie eine Primzahl als Basis, etwa 31, sowie einen großen Primzahlmodul. Der Modulo-Operator hält die Zahlen klein und verhindert Überläufe.

Gehen Sie die Zeichenkette durch und fügen Sie jedes Zeichen mithilfe des Horner-Schemas ein, wobei Sie in jedem Schritt den Modulo-Operator anwenden.

Speichern Sie für jede Position einen Präfix-Hash. Dann lässt sich jeder Teilzeichenketten-Hash durch eine schnelle Subtraktion berechnen.

Berechnen Sie außerdem die Potenzen der Basis im Voraus. Sie bringen die beiden Präfixe beim Subtrahieren auf dieselbe Ausrichtung.

Der Hash von s[l..r] ist die um eine Potenz skalierte Subtraktion zweier Präfix-Hashes. Pro Anfrage konstante Zeit.

Zwei verschiedene Strings können denselben Hash haben – das ist eine Kollision. Das kommt selten vor, aber bei Wettbewerben werden manchmal Eingaben konstruiert, die eine solche Kollision auslösen.

Verwenden Sie zwei unabhängige Moduli und vergleichen Sie beide Hashwerte. Eine gleichzeitige Kollision bei beiden ist praktisch unmöglich.

Hashing ermöglicht den Substring-Vergleich, das Finden von Wiederholungen und die Mustersuche. Es ist ein vielseitiges Schweizer Taschenmesser.

Sie können Strings jetzt in polynomiale Hashwerte umwandeln, jeden Substring in O(1) abfragen und sich gegen Kollisionen absichern. 🚀