So implementieren Sie den KMP-Algorithmus mit Java

So implementieren Sie den KMP-Algorithmus mit Java

Der KMP-Algorithmus (Karp-Miller-Rosenberg-Algorithmus) ist ein String-Matching-Algorithmus, der bereits abgeglichene Informationen verwendet, um unnötige Matchings zu vermeiden und dadurch die Matching-Effizienz zu verbessern. Der KMP-Algorithmus ist ein effizienter Algorithmus für den Umgang mit umfangreichen Text- und Musterzeichenfolgenvergleichen. In diesem Artikel wird die Verwendung von Java zur Implementierung des KMP-Algorithmus vorgestellt und spezifische Codebeispiele gegeben.

1. Prinzip des KMP-Algorithmus
1.1. Präfixfunktion
Die Kernidee des KMP-Algorithmus besteht darin, die Präfixfunktion (auch als längstes gemeinsames Präfix und Suffix bekannt) zu verwenden, um den Sprung der Musterzeichenfolge zu verarbeiten Der Abgleich schlägt fehl.

Die Präfixfunktion ist ein Array pi, wobei pi[i] die Länge des längsten wahren Präfixes und des längsten wahren Suffixes der Zeichenfolge darstellt, die mit dem i-ten Zeichen unter den ersten i Zeichen der Musterzeichenfolge endet. Beispielsweise lautet die Präfixfunktion der Musterzeichenfolge „ababaca“ [0, 0, 1, 2, 3, 0, 1].

1.2. Hauptschritte des KMP-Algorithmus
Die Hauptschritte des KMP-Algorithmus sind wie folgt:
1) Berechnen Sie die Präfixfunktion der Musterzeichenfolge;
2) Passen Sie die Textzeichenfolge an und verwenden Sie die Präfixfunktion, um die Situation zu behandeln Matching-Fehler.

2. Implementierung des KMP-Algorithmus
Im Folgenden stellen wir vor, wie Sie Java zur Implementierung des KMP-Algorithmus verwenden.

public class KMP {
    public static int[] computePrefixFunction(String pattern) {
        int m = pattern.length();
        int[] pi = new int[m];
        int k = 0;
        for (int i = 1; i < m; i++) {
            while (k > 0 && pattern.charAt(k) != pattern.charAt(i)) {
                k = pi[k - 1];
            }
            if (pattern.charAt(k) == pattern.charAt(i)) {
                k++;
            }
            pi[i] = k;
        }
        return pi;
    }

    public static int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] pi = computePrefixFunction(pattern);
        int q = 0;
        for (int i = 0; i < n; i++) {
            while (q > 0 && pattern.charAt(q) != text.charAt(i)) {
                q = pi[q - 1];
            }
            if (pattern.charAt(q) == text.charAt(i)) {
                q++;
            }
            if (q == m) {
                return i - m + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String text = "ababababacaba";
        String pattern = "bac";
        int index = search(text, pattern);
        if (index != -1) {
            System.out.println("Pattern found at index " + index);
        } else {
            System.out.println("Pattern not found");
        }
    }
}

Im obigen Code wird die Funktion „computePrefixFunction“ verwendet, um die Präfixfunktion der Musterzeichenfolge zu berechnen, und die Suchfunktion wird zum Abgleichen in der Textzeichenfolge verwendet. In der Hauptfunktion können wir sehen, wie die Suchfunktion aufgerufen wird, um einen Mustervergleich durchzuführen und die passenden Ergebnisse auszugeben.

3. Zusammenfassung
Durch die Verwendung des KMP-Algorithmus können wir String-Matching-Operationen effektiv durchführen. In diesem Artikel werden das Prinzip des KMP-Algorithmus und die Verwendung von Java zur Implementierung des KMP-Algorithmus vorgestellt. Ich hoffe, dass dieser Artikel Ihnen hilft, den KMP-Algorithmus zu lernen und zu verstehen.

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