# Rabin-Karp Erweiterung für Wildcards



## Kirby.exe (10. Feb 2021)

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 (10. Feb 2021)

Also cih verstehe unter wildcard eher sowas: *

Oder ggf % oder _ je nach syntax


----------



## Kirby.exe (10. Feb 2021)

Mhh also scheinbar habe ich dann etwas missverstanden xD


----------



## fhoffmann (10. Feb 2021)

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 (10. Feb 2021)

Danke


----------

