So implementieren Sie den KMP-Algorithmus in C#

So implementieren Sie den KMP-Algorithmus in C#

Der KMP-Algorithmus (Knuth-Morris-Pratt) ist ein effizienter String-Matching-Algorithmus, der zum Ermitteln der Position von Musterzeichenfolgen in Textzeichenfolgen verwendet wird. Die Kernidee besteht darin, die abgeglichenen Teilinformationen zu verwenden, um unnötige Vergleiche zu vermeiden.

Der Schlüssel zur Implementierung des KMP-Algorithmus besteht darin, eine teilweise Übereinstimmungstabelle (Partial Match Table) zu erstellen, die auch als nächstes Array bezeichnet wird. Dieses Array zeichnet die Länge der längsten passenden Suffix-Teilzeichenfolge jeder Präfix-Teilzeichenfolge in der Musterzeichenfolge auf.

Im Folgenden sind die spezifischen Schritte und Codebeispiele für die Implementierung des KMP-Algorithmus in C# aufgeführt:

Schritt 1: Erstellen Sie eine teilweise übereinstimmende Tabelle.

1. Definieren Sie als Nächstes ein ganzzahliges Array mit einer Größe der Länge der Musterzeichenfolge und initialisieren Sie es next[0] = -1 .
2. Definieren Sie zwei Zeiger i und j mit den Anfangswerten 0 bzw. -1.
3. Bestimmen Sie, ob i das Ende der Musterzeichenfolge erreicht. Wenn nicht, führen Sie die folgenden Schritte aus:
   a. Wenn j gleich -1 ist oder das aktuelle Zeichen gleich dem Zeichen ist, das dem Zeiger j entspricht, werden i und j dies tun gleichzeitig rückwärts bewegt werden, und next[i ] = j.
   b. Bewegen Sie andernfalls den Zeiger j an die Position von next[j] und fahren Sie mit dem Abgleich fort.
4. Geben Sie als Nächstes die erstellte Teilübereinstimmungstabelle zurück.

Das Folgende ist der Code für die Implementierung der obigen Schritte:

private int[] BuildNext(string pattern)
{
    int[] next = new int[pattern.Length];
    next[0] = -1;
    int i = 0, j = -1;
    
    while (i < pattern.Length - 1)
    {
        if (j == -1 || pattern[i] == pattern[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
    
    return next;
}

Schritt 2: Verwenden Sie eine teilweise Übereinstimmungstabelle für den Abgleich.

1. Definieren Sie zwei Zeiger i und j, die auf die Startpositionen der Textzeichenfolge und des Musters zeigen Zeichenfolge bzw.
2. Bestimmen Sie, ob i und j das Ende erreicht haben:
   a. Wenn j gleich -1 ist oder das aktuelle Zeichen dem Zeichen entspricht, das dem Zeiger j entspricht, werden i und j verschoben gleichzeitig rückwärts.
   b. Bewegen Sie andernfalls den Zeiger j an die Position von next[j] und fahren Sie mit dem Abgleich fort.
3. Wenn der Zeiger j auf das Ende der Musterzeichenfolge zeigt, bedeutet dies, dass die Übereinstimmung erfolgreich ist und der Index der Startposition in der Textzeichenfolge zurückgegeben wird.
4. Wenn die Übereinstimmung fehlschlägt, wird -1 zurückgegeben.

Im Folgenden finden Sie den Code zur Implementierung der obigen Schritte:

private int KMP(string text, string pattern)
{
    int[] next = BuildNext(pattern);
    int i = 0, j = 0;
    
    while (i < text.Length && j < pattern.Length)
    {
        if (j == -1 || text[i] == pattern[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    
    if (j == pattern.Length)
    {
        return i - j;
    }
    
    return -1;
}

Durch Aufrufen der KMP-Methode und Übergeben der Textzeichenfolge und Musterzeichenfolge können Sie das übereinstimmende Ergebnis erhalten.

Das Obige sind die Schritte und Codebeispiele zur Implementierung des KMP-Algorithmus in C#. Durch die Verwendung teilweise übereinstimmender Tabellen kann der KMP-Algorithmus die Effizienz des Zeichenfolgenabgleichs effektiv verbessern, insbesondere bei der Verarbeitung großer Textzeichenfolgen und langer Musterzeichenfolgen, und eine bessere Leistung erzielen.

Das obige ist der detaillierte Inhalt vonSo implementieren Sie den KMP-Algorithmus in C#. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!