Einen Text gegeben txt[0 . . . N-1] und ein Muster Bett[0 . . . M-1] , schreiben Sie eine Funktion search(char pat[], char txt[]), die alle Vorkommen von pat[] in txt[] ausgibt. Das können Sie vermuten N > M .

Hashtabelle Java

Beispiele:

Eingang: txt[] = DIES IST EIN TESTTEXT, pat[] = TEST
Ausgabe: Muster gefunden bei Index 10

Eingang: txt[] = DEINE VÄTER
pat[] = AABA
Ausgabe: Muster bei Index 0 gefunden, Muster bei Index 9 gefunden, Muster bei Index 12 gefunden

Eintreffen von Mustern im Text

Wir haben den naiven Mustersuchalgorithmus im besprochen vorherigen Post . Die Worst-Case-Komplexität des Naive-Algorithmus ist O(m(n-m+1)). Die zeitliche Komplexität des KMP-Algorithmus beträgt im schlimmsten Fall O(n+m).

KMP (Knuth Morris Pratt) Mustersuche:

Der Naiver Mustersuchalgorithmus funktioniert nicht gut, wenn viele übereinstimmende Zeichen gefolgt von einem nicht übereinstimmenden Zeichen angezeigt werden.

Beispiele:

1) txt[] = AAAAAAAAAAAAAAAAAAB, pat[] = AAAAB
2) txt[] = ABABABCABABABCABABABC, pat[] = ABABAC (kein schlimmster Fall, aber ein schlechter Fall für Naive)

Der KMP-Matching-Algorithmus nutzt die degenerierende Eigenschaft (Muster mit denselben Untermustern, die mehr als einmal im Muster vorkommen) des Musters und verbessert die Komplexität im ungünstigsten Fall O(n+m) .

Die Grundidee des KMP-Algorithmus ist: Wann immer wir eine Nichtübereinstimmung feststellen (nach einigen Übereinstimmungen), kennen wir bereits einige der Zeichen im Text des nächsten Fensters. Wir nutzen diese Informationen, um eine Übereinstimmung mit Zeichen zu vermeiden, von denen wir wissen, dass sie ohnehin übereinstimmen.

Matching-Übersicht

txt = AAAAABAAABA
pat = AAAA
Wir vergleichen das erste Fenster von txt mit das gleiche

txt = AAAA VATER
gerade = AAAA [Ausgangsposition]
Wir finden eine Übereinstimmung. Das ist dasselbe wie Naives String-Matching .

Im nächsten Schritt vergleichen wir das nächste Fenster von txt mit das gleiche .

txt = AAAAA ZERSTÖREN
gerade = AAAA [Muster um eine Position verschoben]

Hier führt KMP eine Optimierung gegenüber Naive durch. In diesem zweiten Fenster vergleichen wir nur das vierte A des Musters
mit dem vierten Zeichen des aktuellen Textfensters, um zu entscheiden, ob das aktuelle Fenster übereinstimmt oder nicht. Da wir es wissen
Da die ersten drei Zeichen ohnehin übereinstimmen, haben wir die Übereinstimmung der ersten drei Zeichen übersprungen.

Bedarf an Vorverarbeitung?

Aus der obigen Erklärung ergibt sich eine wichtige Frage, wie man weiß, wie viele Zeichen übersprungen werden müssen. Um dies zu wissen,
Wir verarbeiten das Muster vor und bereiten ein Integer-Array lps[] vor, das uns die Anzahl der zu überspringenden Zeichen angibt

Übersicht über die Vorverarbeitung:

• Der KMP-Algorithmus verarbeitet pat[] vor und erstellt ein Hilfsmittel lps[] der Größe M (entspricht der Größe des Musters), mit dem Zeichen beim Abgleich übersprungen werden.
• Name lps gibt das längste richtige Präfix an, das auch ein Suffix ist. Ein richtiges Präfix ist ein Präfix mit einer ganzen Zeichenfolge, die nicht zulässig ist. Präfixe von ABC sind beispielsweise , A, AB und ABC. Richtige Präfixe sind , A und AB. Suffixe der Zeichenfolge sind , C, BC und ABC.
• Wir suchen nach LPS in Untermustern. Genauer gesagt konzentrieren wir uns auf Teilzeichenfolgen von Mustern, die sowohl Präfixe als auch Suffixe sind.
• Für jedes Untermuster pat[0..i] mit i = 0 bis m-1 speichert lps[i] die Länge des maximal passenden richtigen Präfixes, das auch ein Suffix des Untermusters pat[0..i] ist ].

lps[i] = das längste richtige Präfix von pat[0..i], das auch ein Suffix von pat[0..i] ist.

Notiz: lps[i] könnte auch als das längste Präfix definiert werden, das auch ein richtiges Suffix ist. Wir müssen es an einer Stelle richtig verwenden, um sicherzustellen, dass nicht der gesamte Teilstring berücksichtigt wird.

Beispiele für die Konstruktion von lps[]:

Für das Muster AAAA ist lps[] [0, 1, 2, 3]

Für das Muster ABCDE ist lps[] [0, 0, 0, 0, 0]

Für das Muster AABAACAABAA ist lps[] [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]

Für das Muster AAACAAAAAC ist lps[] [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]

Für das Muster AAABAAA ist lps[] [0, 1, 2, 0, 1, 2, 3]

Vorverarbeitungsalgorithmus:

Im Vorverarbeitungsteil

• Wir berechnen Werte in lps[] . Dazu verfolgen wir die Länge des längsten Präfix-Suffix-Werts (wir verwenden nur Variable für diesen Zweck) für den vorherigen Index
• Wir initialisieren lps[0] Und nur als 0.
• Wenn pat[len] Und Betten übereinstimmen, erhöhen wir nur um 1 und weisen Sie den inkrementierten Wert lps[i] zu.
• Wenn pat[i] und pat[len] nicht übereinstimmen und len nicht 0 ist, aktualisieren wir len auf lps[len-1]
• Sehen berechnenLPSArray() Weitere Informationen finden Sie im folgenden Code

Veranschaulichung der Vorverarbeitung (oder Konstruktion von lps[]):

pat[] = AAAAAAA

=> len = 0, i = 0:

Fußnotenabschlag

• lps[0] ist immer 0, wir gehen zu i = 1

=> len = 0, i = 1:

• Da pat[len] und pat[i] übereinstimmen, führen Sie len++ aus,
• Speichern Sie es in lps[i] und führen Sie i++ aus.
• Setze len = 1, lps[1] = 1, i = 2

=> len = 1, i = 2:

• Da pat[len] und pat[i] übereinstimmen, führen Sie len++ aus,
• Speichern Sie es in lps[i] und führen Sie i++ aus.
• Setze len = 2, lps[2] = 2, i = 3

=> len = 2, i = 3:

• Da pat[len] und pat[i] nicht übereinstimmen und len> 0 ist,
• Setze len = lps[len-1] = lps[1] = 1

=> len = 1, i = 3:

• Da pat[len] und pat[i] nicht übereinstimmen und len> 0 ist,
• len = lps[len-1] = lps[0] = 0

=> len = 0, i = 3:

• Da pat[len] und pat[i] nicht übereinstimmen und len = 0 ist,
• Setzen Sie lps[3] = 0 und i = 4

=> len = 0, i = 4:

• Da pat[len] und pat[i] übereinstimmen, führen Sie len++ aus,
• Speichern Sie es in lps[i] und führen Sie i++ aus.
• Setze len = 1, lps[4] = 1, i = 5

=> len = 1, i = 5:

• Da pat[len] und pat[i] übereinstimmen, führen Sie len++ aus,
• Speichern Sie es in lps[i] und führen Sie i++ aus.
• Setze len = 2, lps[5] = 2, i = 6

=> len = 2, i = 6:

• Da pat[len] und pat[i] übereinstimmen, führen Sie len++ aus,
• Speichern Sie es in lps[i] und führen Sie i++ aus.
• len = 3, lps[6] = 3, i = 7

=> len = 3, i = 7:

• Da pat[len] und pat[i] nicht übereinstimmen und len> 0 ist,
• Setze len = lps[len-1] = lps[2] = 2

=> len = 2, i = 7:

• Da pat[len] und pat[i] übereinstimmen, führen Sie len++ aus,
• Speichern Sie es in lps[i] und führen Sie i++ aus.
• len = 3, lps[7] = 3, i = 8

Wir hören hier auf, da wir das gesamte lps[] erstellt haben.

Implementierung des KMP-Algorithmus:

im Gegensatz zu den Naiver Algorithmus Wenn wir das Muster um eins verschieben und alle Zeichen bei jeder Verschiebung vergleichen, verwenden wir einen Wert von lps[], um zu entscheiden, welche Zeichen als nächstes abgeglichen werden sollen. Die Idee besteht darin, kein Zeichen zu finden, von dem wir wissen, dass es trotzdem passt.

Wie verwende ich lps[], um die nächsten Positionen festzulegen (oder um die Anzahl der zu überspringenden Zeichen zu ermitteln)?

• Wir beginnen den Vergleich von pat[j] mit j = 0 mit Zeichen des aktuellen Textfensters.
• Wir gleichen weiterhin die Zeichen txt[i] und pat[j] ab und erhöhen i und j weiter, während pat[j] und txt[i] bestehen bleiben passend .
• Wenn wir einen sehen Nichtübereinstimmung
  • Wir wissen, dass die Zeichen pat[0..j-1] mit txt[i-j…i-1] übereinstimmen (Beachten Sie, dass j mit 0 beginnt und ihn nur erhöht, wenn eine Übereinstimmung vorliegt).
  • Wir wissen auch (aus der obigen Definition), dass lps[j-1] die Anzahl der Zeichen von pat[0…j-1] ist, die sowohl richtige Präfixe als auch Suffixe sind.
  • Aus den beiden oben genannten Punkten können wir schließen, dass wir diese lps[j-1]-Zeichen nicht mit txt[i-j…i-1] abgleichen müssen, da wir wissen, dass diese Zeichen ohnehin übereinstimmen. Betrachten wir das obige Beispiel, um dies zu verstehen.

Nachfolgend finden Sie die Abbildung des obigen Algorithmus:

Betrachten Sie txt[] = AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA , pat[] = AAAA

Wenn wir dem oben beschriebenen LPS-Erstellungsprozess folgen, dann lps[] = {0, 1, 2, 3}

-> i = 0, j = 0: txt[i] und pat[j] stimmen überein, machen i++, j++

-> i = 1, j = 1: txt[i] und pat[j] stimmen überein, machen i++, j++

-> i = 2, j = 2: txt[i] und pat[j] stimmen überein, machen i++, j++

-> i = 3, j = 3: txt[i] und pat[j] stimmen überein, machen i++, j++

-> i = 4, j = 4: Da j = M, Druckmuster gefunden und j zurückgesetzt, J = lps[j-1] = lps[3] = 3

Im Gegensatz zum naiven Algorithmus stimmen wir hier nicht mit den ersten drei überein
Zeichen dieses Fensters. Der Wert von lps[j-1] (im obigen Schritt) gab uns den Index des nächsten passenden Zeichens.

-> i = 4, j = 3: txt[i] und pat[j] stimmen überein, machen i++, j++

-> i = 5, j = 4: Da j == M, Druckmuster gefunden und j zurückgesetzt, J = lps[j-1] = lps[3] = 3
Auch hier stimmen wir im Gegensatz zum naiven Algorithmus nicht mit den ersten drei Zeichen dieses Fensters überein. Der Wert von lps[j-1] (im obigen Schritt) gab uns den Index des nächsten übereinstimmenden Zeichens.

-> i = 5, j = 3: txt[i] und pat[j] stimmen NICHT überein und j> 0, ändere nur j. J = lps[j-1] = lps[2] = 2

-> i = 5, j = 2: txt[i] und pat[j] stimmen NICHT überein und j> 0, ändere nur j. J = lps[j-1] = lps[1] = 1

-> i = 5, j = 1: txt[i] und pat[j] stimmen NICHT überein und j> 0, ändere nur j. J = lps[j-1] = lps[0] = 0

-> i = 5, j = 0: txt[i] und pat[j] stimmen NICHT überein und j ist 0, wir machen i++.

-> i = 6, j = 0: txt[i] und pat[j] stimmen überein, machen i++ und j++

-> i = 7, j = 1: txt[i] und pat[j] stimmen überein, machen i++ und j++

Wir machen so weiter, bis der Text genügend Zeichen enthält, die mit den Zeichen im Muster verglichen werden können …

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

C++

>

>

Java

>

>

Python3

String in booleschen Java umwandeln

>

>

C#

String zum JSON-Objekt

>

>

Javascript

>

>

PHP

>

>

Found pattern at index 10>

Zeitkomplexität: O(N+M) wobei N die Länge des Textes und M die Länge des zu findenden Musters ist.
Hilfsraum: O(M)