Wie funktioniert die Galil-Regel beim Boyer-Moore-Algorithmus?

Ich würde gerne wissen, wie der Textsuchalgorithmus von Boyer-Moore mit Galils Regel funktioniert. Ich habe versucht zu suchen, aber ich konnte die gefundenen Informationen nicht verstehen, zum Beispiel diese Wikipedia-Seite . Und warum gehen wir mit dieser Regel zu einer linearen Zeitkomplexität?

Der Algorithmus basiert auf einem einfachen Prinzip. Angenommen, wir versuchen, einen Teilstring der Länge n abzugleichen  . Wir werden uns zuerst das Zeichen am Index m ansehen. Wenn dieses Zeichen nicht in der Zeichenfolge enthalten ist, wissen wir, dass die gewünschte Teilzeichenfolge nicht in Zeichen an den Indizes  1 2 .... n beginnen kann

Wenn sich dieses Zeichen in unserer Zeichenfolge befindet, gehen wir davon aus, dass es sich an der letzten Stelle in unserer Zeichenfolge befindet, an der es sich befinden kann. Wir werden dann zurückspringen und versuchen, die Zeichenfolge von diesem möglichen Startplatz aus abzugleichen. Diese Information ist meine erste Tabelle.

Sobald ich mit dem Matching am Anfang des Teilstrings beginne und eine Nichtübereinstimmung finde, kann ich nicht einfach von vorne anfangen. Ich könnte teilweise durch ein Match gehen, das an einem anderen Punkt beginnt. Wenn ich zum Beispiel versuche,  anand in ananand  erfolgreich abzugleichen, stelle anan fest , dass das folgende a keine Anzeige ist, aber ich habe gerade eine gefunden, und deshalb sollte ich wieder versuchen, mein drittes Zeichen in meiner Teilzeichenfolge abzugleichen . Die Informationen "Wenn ich nach dem Abgleichen von x Zeichen fehlschlage, könnte ich mich auf dem y-ten Zeichen einer Übereinstimmung befinden" werden in der zweiten Tabelle gespeichert.

Beachten Sie, dass ich, wenn ich nicht mit der zweiten Tabelle übereinstimme, weiß, wie weit ich in einer Übereinstimmung bin, basierend auf dem, was ich gerade gefunden habe. Die erste Tabelle weiß, wie weit ich zurückliegen könnte, basierend auf dem Charakter, den ich gerade gesehen habe und mit dem ich nicht übereinstimmen konnte. Sie möchten die pessimistischere dieser beiden Informationen verwenden.