algorithm
Substring-Suche
Suche…
KMP-Algorithmus in C
Bei einem gegebenen Text txt und ein Muster pat, wird das Ziel dieses Programms alle Vorkommen von pat in txt zu drucken.
Beispiele:
Eingang:
txt[] = "THIS IS A TEST TEXT"
pat[] = "TEST"
Ausgabe:
Pattern found at index 10
Eingang:
txt[] = "AABAACAADAABAAABAA"
pat[] = "AABA"
Ausgabe:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13
C-Sprachimplementierung:
// C program for implementation of KMP pattern searching
// algorithm
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
void computeLPSArray(char *pat, int M, int *lps);
void KMPSearch(char *pat, char *txt)
{
int M = strlen(pat);
int N = strlen(txt);
// create lps[] that will hold the longest prefix suffix
// values for pattern
int *lps = (int *)malloc(sizeof(int)*M);
int j = 0; // index for pat[]
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
while (i < N)
{
if (pat[j] == txt[i])
{
j++;
i++;
}
if (j == M)
{
printf("Found pattern at index %d \n", i-j);
j = lps[j-1];
}
// mismatch after j matches
else if (i < N && pat[j] != txt[i])
{
// Do not match lps[0..lps[j-1]] characters,
// they will match anyway
if (j != 0)
j = lps[j-1];
else
i = i+1;
}
}
free(lps); // to avoid memory leak
}
void computeLPSArray(char *pat, int M, int *lps)
{
int len = 0; // length of the previous longest prefix suffix
int i;
lps[0] = 0; // lps[0] is always 0
i = 1;
// the loop calculates lps[i] for i = 1 to M-1
while (i < M)
{
if (pat[i] == pat[len])
{
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0)
{
// This is tricky. Consider the example
// AAACAAAA and i = 7.
len = lps[len-1];
// Also, note that we do not increment i here
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
// Driver program to test above function
int main()
{
char *txt = "ABABDABACDABABCABAB";
char *pat = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}
Ausgabe:
Found pattern at index 10
Referenz:
http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/
Einführung in den Rabin-Karp-Algorithmus
Der Rabin-Karp-Algorithmus ist ein von Richard M. Karp und Michael O. Rabin entwickelter String-Suchalgorithmus, der Hashes verwendet, um einen beliebigen Satz von Musterzeichenfolgen in einem Text zu finden.
Eine Teilzeichenfolge einer Zeichenfolge ist eine andere Zeichenfolge, die in vorkommt. Ver ist beispielsweise eine Teilzeichenfolge von stackoverflow . Nicht mit Untersequenz zu verwechseln, weil cover eine Untersequenz derselben Zeichenfolge ist. Mit anderen Worten, jede Untermenge aufeinanderfolgender Buchstaben in einer Zeichenfolge ist eine Teilzeichenfolge der angegebenen Zeichenfolge.
Im Rabin-Karp-Algorithmus generieren wir einen Hash unseres Musters , nach dem wir suchen, und prüfen, ob der rollende Hash unseres Textes dem Muster entspricht oder nicht. Wenn es nicht passt, können wir garantieren, dass das Muster nicht im Text vorhanden ist . Wenn es jedoch nicht trifft, kann das Muster im Text vorhanden sein. Schauen wir uns ein Beispiel an:
Nehmen wir an, wir haben einen Text: yeminsajid und wir möchten herausfinden, ob das Muster nsa im Text vorhanden ist. Um den Hash und den rollenden Hash zu berechnen, müssen wir eine Primzahl verwenden. Dies kann eine beliebige Primzahl sein. Nehmen wir für dieses Beispiel prim = 11 an. Wir ermitteln den Hashwert anhand dieser Formel:
(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......
Wir bezeichnen:
a -> 1 g -> 7 m -> 13 s -> 19 y -> 25
b -> 2 h -> 8 n -> 14 t -> 20 z -> 26
c -> 3 i -> 9 o -> 15 u -> 21
d -> 4 j -> 10 p -> 16 v -> 22
e -> 5 k -> 11 q -> 17 w -> 23
f -> 6 l -> 12 r -> 18 x -> 24
Der Hashwert von nsa lautet :
14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344
Jetzt finden wir den rollenden Hash unseres Textes. Wenn der rollende Hashwert mit dem Hashwert unseres Musters übereinstimmt, prüfen wir, ob die Zeichenfolgen übereinstimmen oder nicht. Da unser Muster 3 Buchstaben hat, werden wir ersten 3 Buchstaben yem aus unserem Text nehmen und Hash - Wert berechnen. Wir bekommen:
25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653
Dieser Wert stimmt nicht mit dem Hashwert unseres Musters überein. Der String existiert also hier nicht. Nun müssen wir den nächsten Schritt prüfen. Um den Hashwert unseres nächsten String- Emis zu berechnen. Wir können dies mit unserer Formel berechnen. Das wäre aber eher trivial und kostet uns mehr. Stattdessen verwenden wir eine andere Technik.
- Wir subtrahieren den Wert des ersten Buchstabens der vorherigen Zeichenfolge von unserem aktuellen Hashwert. In diesem Fall ist y . Wir erhalten
1653 - 25 = 1628. - Wir teilen den Unterschied mit unserer Primzahl , die für dieses Beispiel 11 beträgt. Wir erhalten
1628 / 11 = 148. - Wir fügen den neuen Buchstaben X (Prim) ¹ hinzu , wobei m die Länge des Musters ist, mit dem Quotienten, der i = 9 ist . Wir erhalten
148 + 9 X 11² = 1237.
Der neue Hashwert entspricht nicht unserem Muster-Hashwert. Weiter, für n bekommen wir:
Previous String: emi
First Letter of Previous String: e(5)
New Letter: n(14)
New String: "min"
1237 - 5 = 1232
1232 / 11 = 112
112 + 14 X 11² = 1806
Es passt nicht zusammen. Danach erhalten wir für s :
Previous String: min
First Letter of Previous String: m(13)
New Letter: s(19)
New String: "ins"
1806 - 13 = 1793
1793 / 11 = 163
163 + 19 X 11² = 2462
Es passt nicht zusammen. Als nächstes für ein, erhalten wir:
Previous String: ins
First Letter of Previous String: i(9)
New Letter: a(1)
New String: "nsa"
2462 - 9 = 2453
2453 / 11 = 223
223 + 1 X 11² = 344
Es ist ein Spiel! Jetzt vergleichen wir unser Muster mit dem aktuellen String. Da beide Zeichenfolgen übereinstimmen, ist die Teilzeichenfolge in dieser Zeichenfolge vorhanden. Und wir geben die Startposition unseres Teilstrings zurück.
Der Pseudo-Code lautet:
Hash-Berechnung:
Procedure Calculate-Hash(String, Prime, x):
hash := 0 // Here x denotes the length to be considered
for m from 1 to x // to find the hash value
hash := hash + (Value of String[m])ᵐ⁻¹
end for
Return hash
Hash-Neuberechnung:
Procedure Recalculate-Hash(String, Curr, Prime, Hash):
Hash := Hash - Value of String[Curr] //here Curr denotes First Letter of Previous String
Hash := Hash / Prime
m := String.length
New := Curr + m - 1
Hash := Hash + (Value of String[New])ᵐ⁻¹
Return Hash
String-Übereinstimmung:
Procedure String-Match(Text, Pattern, m):
for i from m to Pattern-length + m - 1
if Text[i] is not equal to Pattern[i]
Return false
end if
end for
Return true
Rabin-Karp:
Procedure Rabin-Karp(Text, Pattern, Prime):
m := Pattern.Length
HashValue := Calculate-Hash(Pattern, Prime, m)
CurrValue := Calculate-Hash(Pattern, Prime, m)
for i from 1 to Text.length - m
if HashValue == CurrValue and String-Match(Text, Pattern, i) is true
Return i
end if
CurrValue := Recalculate-Hash(String, i+1, Prime, CurrValue)
end for
Return -1
Wenn der Algorithmus keine Übereinstimmung findet, gibt er einfach -1 zurück .
Dieser Algorithmus wird zur Erkennung von Plagiaten verwendet. Bei gegebenem Ausgangsmaterial kann der Algorithmus ein Papier schnell nach Instanzen von Sätzen aus dem Ausgangsmaterial durchsuchen, wobei Details wie Groß- und Kleinschreibung und Interpunktion ignoriert werden. Aufgrund der Fülle der gesuchten Zeichenfolgen sind Suchalgorithmen mit einer einzigen Zeichenfolge hier nicht praktikabel. Der Knuth-Morris-Pratt-Algorithmus oder der Boyer-Moore-String-Suchalgorithmus ist ein schnellerer Suchalgorithmus für die Suche nach einem Musterstring als der von Rabin-Karp . Es ist jedoch ein Algorithmus der Wahl für die Suche nach mehreren Mustern. Wenn Sie eines der großen Muster, beispielsweise k, mit fester Länge in einem Text finden möchten, können Sie eine einfache Variante des Rabin-Karp-Algorithmus erstellen.
Für Text der Länge n und p Muster der kombinierten Länge m ist die durchschnittliche und beste Laufzeit im Raum O (p) O (n + m ) , aber die Zeit im ungünstigsten Fall ist O (nm) .
Einführung in den Knuth-Morris-Pratt-Algorithmus (KMP)
Angenommen, wir haben einen Text und ein Muster . Wir müssen feststellen, ob das Muster im Text vorhanden ist oder nicht. Zum Beispiel:
+-------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+---+---+---+---+---+---+---+---+
| Text | a | b | c | b | c | g | l | x |
+-------+---+---+---+---+---+---+---+---+
+---------+---+---+---+---+
| Index | 0 | 1 | 2 | 3 |
+---------+---+---+---+---+
| Pattern | b | c | g | l |
+---------+---+---+---+---+
Dieses Muster existiert im Text . Unsere Teilzeichenfolgen-Suche sollte also 3 zurückgeben , den Index der Position, von der dieses Muster ausgeht. Wie funktioniert also unser Brute-Force-Teilstringsuchverfahren?
Was wir normalerweise tun, ist: Wir beginnen mit dem 0. Index des Textes und dem 0. Index unseres * Musters und vergleichen Text [0] mit Muster [0] . Da sie nicht übereinstimmen, gehen wir zum nächsten Index unseres Textes und vergleichen Text [1] mit Muster [0] . Da dies eine Übereinstimmung ist, erhöhen wir auch den Index unseres Musters und den Index des Textes . Wir vergleichen Text [2] mit Muster [1] . Sie passen auch zusammen. Nach dem gleichen Verfahren vergleichen wir nun Text [3] mit Muster [2] . Da sie nicht übereinstimmen, beginnen wir an der nächsten Position, an der wir das Spiel gefunden haben. Das ist Index 2 des Textes . Wir vergleichen Text [2] mit Muster [0] . Sie passen nicht zusammen. Inkrementieren des Index des Textes , vergleichen wir Text [3] mit Muster [0] . Sie passen. Wieder stimmen Text [4] und Muster [1] überein, Text [5] und Muster [2] stimmen überein und Text [6] und Muster [3] stimmen überein. Seitdem wir das Ende unseres Patterns erreicht haben , geben wir jetzt den Index zurück, von dem unser Match angefangen hat, nämlich 3 . Wenn unser Muster : bcgll , das heißt, wenn das Muster in unserem Text nicht vorhanden ist, sollte unsere Suche eine Ausnahme oder -1 oder einen anderen vordefinierten Wert zurückgeben. Wir können deutlich erkennen, dass dieser Algorithmus im ungünstigsten Fall eine O(mn) wobei m die Länge des Textes und n die Länge des Musters ist . Wie reduzieren wir diese zeitliche Komplexität? Hier kommt der KMP-Substring-Suchalgorithmus ins Spiel.
Der String-Suchalgorithmus von Knuth-Morris-Pratt oder der KMP-Algorithmus sucht nach Vorkommen eines "Musters" in einem Haupt- "Text", indem er die Beobachtung verwendet, dass das Wort selbst bei Auftreten einer Nichtübereinstimmung ausreichend Informationen enthält, um zu bestimmen, wo die nächste Übereinstimmung beginnen könnte und umgeht damit eine erneute Überprüfung zuvor übereinstimmender Zeichen. Der Algorithmus wurde 1970 von Donuld Knuth und Vaughan Pratt und unabhängig von James H. Morris konzipiert . Das Trio veröffentlichte es 1977 gemeinsam.
Lassen Sie uns unser Beispiel Text und Muster für ein besseres Verständnis erweitern:
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| Index |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|13|14|15|16|17|18|19|20|21|22|
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| Text |a |b |c |x |a |b |c |d |a |b |x |a |b |c |d |a |b |c |d |a |b |c |y |
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | y |
+---------+---+---+---+---+---+---+---+---+
Zuerst stimmen Text und Muster bis Index 2 überein. Text [3] und Muster [3] stimmen nicht überein. Unser Ziel ist es also, in diesem Text nicht rückwärts zu gehen, das heißt, im Fall einer Nichtübereinstimmung möchten wir nicht, dass unser Matching wieder von der Position beginnt, mit der wir angefangen haben. Um dies zu erreichen, suchen wir in unserem Pattern nach einem Suffix, bevor unser Mismatch aufgetreten ist (substring abc ). Dies ist auch ein Präfix des substrings unseres Patterns . Da in unserem Beispiel alle Zeichen eindeutig sind, gibt es kein Suffix. Dies ist das Präfix unserer übereinstimmenden Teilzeichenfolge. Das heißt also, unser nächster Vergleich beginnt mit Index 0 . Warten Sie ein bisschen, Sie werden verstehen, warum wir das getan haben. Als Nächstes vergleichen wir Text [3] mit Muster [0] und er stimmt nicht überein. Danach finden wir für Text von Index 4 bis Index 9 und für Muster von Index 0 bis Index 5 eine Übereinstimmung. Wir finden eine Abweichung in Text [10] und Muster [6] . Wir nehmen also den Teilstring aus Pattern direkt vor dem Punkt, an dem ein Konflikt auftritt (Teilstring abcdabc ), und prüfen auf ein Suffix, das auch ein Präfix dieses Teilstrings ist. Wir können hier sehen, ab ist sowohl das Suffix als auch das Präfix dieses Teilstrings. Das bedeutet, da wir bis Text [10] übereinstimmen, sind die Zeichen unmittelbar vor dem Konflikt nicht korrekt . Was können wir daraus folgern ist , dass da ab auch ein Präfix der Teilkette ist , die wir haben, wir müssen nicht ab wieder überprüfen und die nächste Prüfung von Text beginnen [10] und Pattern [2]. Wir mussten nicht auf den gesamten Text zurückblicken, wir können direkt dort anfangen, wo unser Missverhältnis aufgetreten ist. Jetzt prüfen wir Text [10] und Pattern [2] , da dies eine Nichtübereinstimmung ist und der Teilstring vor Nichtübereinstimmung ( abc ) kein Suffix enthält, das auch ein Präfix ist. Wir überprüfen Text [10] und Muster [0] . sie passen nicht zusammen Danach für Text von Index 11 bis Index 17 und für Pattern von Index 0 bis Index 6 . Wir finden eine Abweichung in Text [18] und Muster [7] . Also überprüfen wir noch einmal den Teilstring vor dem Konflikt (Teilstring abcdabc ) und finden, dass abc sowohl das Suffix als auch das Präfix ist. Da wir also bis Pattern [7] übereinstimmten, muss abc vor Text [18] stehen . Das bedeutet, dass wir erst Text [17] vergleichen müssen, und unser Vergleich beginnt mit Text [18] und Muster [3] . So finden wir ein Match und wir geben 15 zurück, was unser Startindex für das Match ist. So funktioniert unsere KMP-Substringsuche mit Suffix- und Präfixinformationen.
Wie können wir nun effizient berechnen, ob das Suffix mit dem Präfix identisch ist und an welcher Stelle die Prüfung beginnt, wenn zwischen Text und Muster ein Zeichenfehler vorliegt . Schauen wir uns ein Beispiel an:
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Wir erzeugen ein Array mit den erforderlichen Informationen. Nennen wir das Array S. Die Größe des Arrays entspricht der Länge des Musters. Da der erste Buchstabe des Patterns kein Suffix eines Präfixes sein darf, setzen wir S [0] = 0 . Wir nehmen zunächst i = 1 und j = 0 . Bei jedem Schritt vergleichen wir Muster [i] und Muster [j] und erhöhen i . Wenn es eine Übereinstimmung gibt, setzen wir S [i] = j + 1 und erhöhen j , wenn es keine Übereinstimmung gibt, überprüfen wir die vorherige Werteposition von j (falls verfügbar) und setzen j = S [j-1] (wenn j ist ungleich 0 ), so lange, bis S [j] nicht mit S [i] übereinstimmt oder j nicht 0 wird . Für das spätere setzen wir S [i] = 0 . Für unser Beispiel:
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
Muster [j] und Muster [i] stimmen nicht überein. Daher erhöhen wir i und da j 0 ist , überprüfen wir den vorherigen Wert nicht und setzen Muster [i] = 0 . Wenn wir i weiter erhöhen, erhalten wir für i = 4 eine Übereinstimmung, also setzen wir S [i] = S [4] = j + 1 = 0 + 1 = 1 und erhöhen j und i . Unser Array wird wie folgt aussehen:
j i
+---------+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| Pattern | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | | | |
+---------+---+---+---+---+---+---+---+---+
Da Muster [1] und Muster [5] eine Übereinstimmung sind, setzen wir S [i] = S [5] = j + 1 = 1 + 1 = 2 . Wenn wir fortfahren, finden wir eine Nichtübereinstimmung für j = 3 und i = 7 . Da j nicht gleich 0 ist , setzen wir j = S [j-1] . Und wir vergleichen die Zeichen bei i und j sind gleich oder nicht, da sie gleich sind, setzen wir S [i] = j + 1. Unser abgeschlossenes Array sieht folgendermaßen aus:
+---------+---+---+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+
Dies ist unser erforderliches Array. Hier bedeutet ein Nicht-Null-Wert von S [i] , dass es ein S [i] -Längen-Suffix gibt, das mit dem Präfix in diesem Teilstring (Teilstring von 0 bis i ) identisch ist, und der nächste Vergleich beginnt an der Position S [i] + 1 von Muster Unser Algorithmus zur Generierung des Arrays würde folgendermaßen aussehen:
Procedure GenerateSuffixArray(Pattern):
i := 1
j := 0
n := Pattern.length
while i is less than n
if Pattern[i] is equal to Pattern[j]
S[i] := j + 1
j := j + 1
i := i + 1
else
if j is not equal to 0
j := S[j-1]
else
S[i] := 0
i := i + 1
end if
end if
end while
Die Zeitkomplexität zum Erstellen dieses Arrays beträgt O(n) und die Platzkomplexität ist ebenfalls O(n) . Um sicherzustellen, dass Sie den Algorithmus vollständig verstanden haben, versuchen Sie, ein Array für das Muster aabaabaa zu generieren, und prüfen Sie, ob das Ergebnis mit diesem übereinstimmt.
Führen wir nun eine Teilzeichenfolge mit dem folgenden Beispiel aus:
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
| Text | a | b | x | a | b | c | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
+---------+---+---+---+---+---+---+
| Index | 0 | 1 | 2 | 3 | 4 | 5 |
+---------+---+---+---+---+---+---+
| Pattern | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+
| S | 0 | 0 | 0 | 1 | 2 | 0 |
+---------+---+---+---+---+---+---+
Wir haben einen Text , ein Muster und ein vorberechnetes Array S unter Verwendung unserer zuvor definierten Logik. Wir vergleichen Text [0] und Muster [0] und sie sind gleich. Text [1] und Muster [1] sind gleich. Text [2] und Muster [2] stimmen nicht überein. Wir prüfen den Wert an der Position direkt vor der Nichtübereinstimmung. Da S [1] 0 ist , gibt es kein Suffix, das dem Präfix in unserem Teilstring entspricht, und unser Vergleich beginnt an Position S [1] , die 0 ist . Also ist Pattern [0] nicht gleich Text [2] , also machen wir weiter. Text [3] ist identisch mit Muster [0] und es gibt eine Übereinstimmung bis Text [8] und Muster [5] . Wir gehen einen Schritt zurück in das S- Array und suchen 2 . Dies bedeutet, dass es ein Präfix der Länge 2 gibt, das auch das Suffix dieses Teilstrings ( abcab) ist, der ab ist . Das bedeutet auch, dass vor Text [8] ein Abstrich steht . So können wir Pattern [0] und Pattern [1] ignorieren und den nächsten Vergleich mit Pattern [2] und Text [8] beginnen . Wenn wir fortfahren, finden wir das Muster im Text . Unser Verfahren wird wie folgt aussehen:
Procedure KMP(Text, Pattern)
GenerateSuffixArray(Pattern)
m := Text.Length
n := Pattern.Length
i := 0
j := 0
while i is less than m
if Pattern[j] is equal to Text[i]
j := j + 1
i := i + 1
if j is equal to n
Return (j-i)
else if i < m and Pattern[j] is not equal t Text[i]
if j is not equal to 0
j = S[j-1]
else
i := i + 1
end if
end if
end while
Return -1
Die zeitliche Komplexität dieses Algorithmus ist, abgesehen von der Suffix-Array-Berechnung, O(m) . Da GenerateSuffixArray O(n) , beträgt die Gesamtzeitkomplexität des KMP-Algorithmus: O(m+n) .
PS: Wenn Sie mehrere Vorkommen von Pattern im Text suchen möchten, geben Sie den Wert aus, anstatt ihn zurückzugeben. Speichern Sie ihn und setzen Sie j := S[j-1] . Behalten Sie ein flag zu verfolgen, ob Sie ein Vorkommen gefunden haben oder nicht, und behandeln Sie es entsprechend.
Python-Implementierung des KMP-Algorithmus.
Heuhaufen : Die Zeichenfolge, in der ein bestimmtes Muster gesucht werden muss.
Nadel : Das zu durchsuchende Muster.
Zeitkomplexität : Der Suchabschnitt (strstr-Methode) hat die Komplexität O (n), wobei n die Länge des Heuhakens ist, aber da die Nadel auch für das Erstellen der Präfixtabelle vorbereitet wird, ist O (m) erforderlich, um die Präfixtabelle zu erstellen, wobei m die Länge von ist Die Nadel.
Daher ist die Gesamtzeitkomplexität für KMP O (n + m).
Raumkomplexität : O (m) wegen Präfix-Tabelle auf der Nadel.
Hinweis: Bei der folgenden Implementierung wird die Startposition der Übereinstimmung im Heuhaufen zurückgegeben (wenn eine Übereinstimmung vorhanden ist). Andernfalls wird -1 zurückgegeben. Für Randfälle, z. B. wenn Nadel / Heuhaufen eine leere Schnur ist oder im Heuhaufen keine Nadel gefunden wird.
def get_prefix_table(needle):
prefix_set = set()
n = len(needle)
prefix_table = [0]*n
delimeter = 1
while(delimeter<n):
prefix_set.add(needle[:delimeter])
j = 1
while(j<delimeter+1):
if needle[j:delimeter+1] in prefix_set:
prefix_table[delimeter] = delimeter - j + 1
break
j += 1
delimeter += 1
return prefix_table
def strstr(haystack, needle):
# m: denoting the position within S where the prospective match for W begins
# i: denoting the index of the currently considered character in W.
haystack_len = len(haystack)
needle_len = len(needle)
if (needle_len > haystack_len) or (not haystack_len) or (not needle_len):
return -1
prefix_table = get_prefix_table(needle)
m = i = 0
while((i<needle_len) and (m<haystack_len)):
if haystack[m] == needle[i]:
i += 1
m += 1
else:
if i != 0:
i = prefix_table[i-1]
else:
m += 1
if i==needle_len and haystack[m-1] == needle[i-1]:
return m - needle_len
else:
return -1
if __name__ == '__main__':
needle = 'abcaby'
haystack = 'abxabcabcaby'
print strstr(haystack, needle)