Rabin-Karp Erweiterung für Wildcards

[Kirby.exe]

Also ich soll beschreiben, wie man den Rabin-Karp Algorithmus ändern muss damit Wildcards unterstützt werden.

Der Standart Rabin-Karp Algorithmus hat ja eine art Mapping Tabelle, wo auf jeden verwendeten Buchstaben eine Zahl gemapped wird.

Dann sondiert man das Hashing z.B. mittels

mappedValue * numberOfElementsInAlphabet^(pattern.length-1)

Dies tut man ja für den gesamten betrachteten Ausschnitt des Haupt Wortes.

Eine Wildcard wäre ja z.b. sowas "\\w" sprich einen Buchstaben aus dem Alphabet. Aber wie könnte ich hier dann einen Wert zu mappen.

Ich muss ja am Anfang des ganzen einmal einen Hash-Wert für mein Pattern erstellen und ich wüsste nicht worauf ich diese Wildcard mappen soll xD

 

[thecain]

Also cih verstehe unter wildcard eher sowas: *

Oder ggf % oder _ je nach syntax

 

[Kirby.exe]

Mhh also scheinbar habe ich dann etwas missverstanden xD

 

[fhoffmann]

An der Stelle des wildcards darf ja ein beliebiger Buchstabe stehen.
Ich würde diese Stelle mit dem Wert 0 in Hashcode berücksichtigen.
Bei deinem Pattern ist dies einfach.
Bei dem durchsuchten Text musst du dann den passenden Wert der Stelle, an der der wildcard steht, vom hash abziehen.
Steht also der wildcard and der k-ten Stelle (von hinten), so musst du wert_des_Zeichens * basis^k vom hash abziehen bevor du vergleichst.

 

[Kirby.exe]

Danke