So implementieren Sie einen String-Matching-Algorithmus mit Java

So verwenden Sie Java, um einen String-Matching-Algorithmus zu implementieren

Einführung:
Der String-Matching-Algorithmus ist ein häufiges Problem im Computerbereich und wird verwendet, um die Vorkommensposition einer bestimmten Musterzeichenfolge in einer Hauptzeichenfolge zu ermitteln. In der tatsächlichen Entwicklung ist es häufig erforderlich, Zeichenfolgen abzugleichen, z. B. bei der Suchfunktion in Texteditoren, beim Schlüsselwortabgleich in Suchmaschinen usw. In diesem Artikel werden mehrere gängige String-Matching-Algorithmen vorgestellt und entsprechende Java-Codebeispiele bereitgestellt.

1. Brute-Force-Matching-Algorithmus
Der Brute-Force-Matching-Algorithmus, auch als naiver Matching-Algorithmus bekannt, ist der grundlegendste String-Matching-Algorithmus. Sein Prinzip ist sehr einfach, das heißt, es vergleicht von jeder Position in der Hauptzeichenfolge Zeichen für Zeichen mit der Musterzeichenfolge, bis ein nicht übereinstimmendes Zeichen erscheint oder eine Übereinstimmung erfolgreich gefunden wird.

Der spezifische Implementierungscode lautet wie folgt:

public class BruteForceMatcher {
    public int match(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }
            if (j == m) {
                return i;
            }
        }
        return -1;
    }
}

2. KMP-Algorithmus
Der KMP-Algorithmus ist ein effizienter String-Matching-Algorithmus. Er verwendet teilweise übereinstimmende Informationen von Musterstrings, um unnötige Zeichenvergleiche zu vermeiden. Der Kern des KMP-Algorithmus besteht darin, ein nächstes Array zu erstellen, um die Länge des längsten gemeinsamen Suffixes an jeder Position in der Musterzeichenfolge aufzuzeichnen.

Der spezifische Implementierungscode lautet wie folgt:

public class KMPMatcher {
    public int match(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] next = getNext(pattern);
        int i = 0, j = 0;
        while (i < n && j < m) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == m) {
            return i - j;
        } else {
            return -1;
        }
    }

    private int[] getNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = -1;
        int i = 0, j = -1;
        while (i < m - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (pattern.charAt(i) != pattern.charAt(j)) {
                    next[i] = j;
                } else {
                    next[i] = next[j];
                }
            } else {
                j = next[j];
            }
        }
        return next;
    }
}

3. Boyer-Moore-Algorithmus
Der Boyer-Moore-Algorithmus ist ein effizienter String-Matching-Algorithmus, der die Zeichenverteilungsinformationen und Rückwärtsverschiebungsregeln in der Musterzeichenfolge nutzt.

Der spezifische Implementierungscode lautet wie folgt:

public class BMMatcher {
    public int match(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] bmBc = preBmBc(pattern);
        int[] bmGs = preBmGs(pattern);
        int j = 0;
        while (j <= n - m) {
            int i;
            for (i = m - 1; i >= 0 && pattern.charAt(i) == text.charAt(i + j); i--);
            if (i < 0) {
                return j;
            } else {
                j += Math.max(bmGs[i], bmBc[text.charAt(i + j)] - m + 1 + i);
            }
        }
        return -1;
    }

    private int[] preBmBc(String pattern) {
        int[] bmBc = new int[256];
        int m = pattern.length();
        for (int i = 0; i < 256; i++) {
            bmBc[i] = m;
        }
        for (int i = 0; i < m - 1; i++) {
            bmBc[pattern.charAt(i)] = m - 1 - i;
        }
        return bmBc;
    }

    private int[] preBmGs(String pattern) {
        int m = pattern.length();
        int[] bmGs = new int[m];
        int i = m - 1, j = m;
        bmGs[m - 1] = m;
        while (i >= 0) {
            if (pattern.charAt(i) == pattern.charAt(j)) {
                bmGs[--i] = --j;
            } else {
                j = m - 1 - i;
                while (j < m && pattern.charAt(m - 1 - j) == pattern.charAt(j)) {
                    j++;
                }
                bmGs[i] = j;
            }
        }
        return bmGs;
    }
}

Schlussfolgerung:
Das Obige sind Codebeispiele für drei gängige String-Matching-Algorithmen, nämlich den Brute-Force-Matching-Algorithmus, den KMP-Algorithmus und den Boyer-Moore-Algorithmus. In praktischen Anwendungen können geeignete Algorithmen entsprechend den spezifischen Anforderungen ausgewählt werden, um die Matching-Effizienz zu verbessern.

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