C-Programm des Rabin-Karp-Algorithmus zur Mustersuche

Mustervergleich in C - Wir müssen herausfinden, ob ein String in einem anderen String existiert, zum Beispiel existiert der String „Algorithmus“ im String „naiver Algorithmus“. Wenn es gefunden wird, wird sein Standort (d. h. wo es sich befindet) angezeigt. Wir neigen dazu, eine Funktion zu erstellen, die ein Array aus zwei Zeichen annimmt und bei einer Übereinstimmung die Position zurückgibt Andernfalls wird -1 zurückgegeben.

Input: txt = "HERE IS A NICE CAP"
   pattern = "NICE"
Output: Pattern found at index 10
Input: txt = "XYZXACAADXYZXYZX"
   pattern = "XYZX"
Output: Pattern found at index 0
   Pattern found at index 9
   Pattern found at index 12

Rabin-Karp ist ein weiterer Mustersuchalgorithmus. Nur String-Matching Von Rabin und Karp vorgeschlagener Algorithmus zur effizienteren Mustersuche Weg. Wie der naive Algorithmus prüft er auch, ob Muster vorliegen, indem er das Fenster verschiebt Es sucht nacheinander nach Hashes, muss jedoch nicht in allen Fällen alle Zeichen überprüfen. Wenn die Hashes übereinstimmen, wird jedes Zeichen überprüft. Auf diese Weise gibt es nur einen Vergleich pro Textteilsequenz, was den Mustersuchalgorithmus effizienter macht.

Vorverarbeitungszeit – O(m)

Die zeitliche Komplexität des Rabin-Karp-Algorithmus beträgt O(m+n), aber im schlimmsten Fall Es ist O(mn).

Algorithmus

rabinkarp_algo(text,pattern,prime)

Eingabe

rabinkarp_algo(text,muster,prime)

Das obige ist der detaillierte Inhalt vonC-Programm des Rabin-Karp-Algorithmus zur Mustersuche. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!