So implementieren Sie den Boyer-Moore-Algorithmus mit Java

So implementieren Sie den Boyer-Moore-Algorithmus mit Java

Einführung:
In der Informatik ist der String-Abgleich eine häufige Aufgabe. Der String-Matching-Algorithmus ist der Schlüssel zur Lösung dieses Problems. Einer der effizienten String-Matching-Algorithmen ist der Boyer-Moore-Algorithmus. In diesem Artikel wird erläutert, wie Sie diesen Algorithmus mithilfe der Java-Sprache implementieren, und es werden spezifische Codebeispiele angehängt.

Prinzip des Boyer-Moore-Algorithmus:
Der Boyer-Moore-Algorithmus ist ein Multi-Pattern-String-Matching-Algorithmus. Er vervollständigt den Matching, indem er die Muster-Strings vorverarbeitet und gute Suffixregeln mit schlechten Zeichenregeln kombiniert. Die Kernidee besteht darin, nicht übereinstimmende Zeichen während des Abgleichvorgangs zwischen der Musterzeichenfolge und der abzugleichenden Zeichenfolge so weit wie möglich zu überspringen und dadurch die Abgleichseffizienz zu verbessern.

Spezifische Implementierungsschritte:

1. Musterzeichenfolge vorverarbeiten:
   Zuerst müssen wir die Musterzeichenfolge vorverarbeiten und zwei Arrays generieren: ein Array für fehlerhafte Zeichen und ein Array für gute Suffixe.

   • Array fehlerhafter Zeichen: Speichert die Position ganz rechts jedes Zeichens in der Musterzeichenfolge.
   • Gutes Suffix-Array: Zeichnen Sie die Position des Suffix-Teilstrings der Musterzeichenfolge ganz rechts in der Musterzeichenfolge auf und zeichnen Sie auf, ob dieser Teilstring mit dem Präfix der Musterzeichenfolge übereinstimmt.

2. Matching-Prozess:
   Während des Matching-Prozesses beginnen wir mit dem Matching vorwärts vom Ende der abzugleichenden Zeichenfolge.

   • Richten Sie zunächst das Ende der Musterzeichenfolge mit dem Ende der abzugleichenden Zeichenfolge aus und versuchen Sie, eine Übereinstimmung herzustellen.
   • Wenn der Abgleich erfolgreich ist, wird die Startposition des Abgleichs zurückgegeben. Andernfalls wird die Position der Musterzeichenfolge gemäß den Regeln für schlechte Zeichen und gute Suffixe verschoben, um den Abgleich fortzusetzen.

Der spezifische Code lautet wie folgt:

import java.util.Arrays;

public class BoyerMoore {

    private static final int NO_OF_CHARS = 256;

    private int[] badCharShift;
    private int[] suffixShift;
    private boolean[] goodSuffix;

    public void preProcessPattern(String pattern) {
        int m = pattern.length();
        // 初始化数组
        badCharShift = new int[NO_OF_CHARS];
        suffixShift = new int[m + 1];
        goodSuffix = new boolean[m + 1];

        Arrays.fill(badCharShift, -1);
        for (int i = 0; i < m; i++) {
            badCharShift[pattern.charAt(i)] = i;
        }

        int f = 0;
        int g = 0;
        suffixShift[m] = m + 1;

        for (int i = m - 1; i >= 0; i--) {
            if (i > f && suffixShift[i + m - f] < i - f) {
                suffixShift[i] = suffixShift[i + m - f];
            } else {
                if (i < f) {
                    f = i;
                }
                g = i;
                while (f >= 0 && pattern.charAt(f) == pattern.charAt(f + m - g)) {
                    f--;
                }
                suffixShift[i] = g - f;
            }
        }

        for (int i = 0; i < m; i++) {
            goodSuffix[i] = suffixShift[i] > m - i;
        }
    }

    public int search(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int i = 0;

        while (i <= n - m) {
            int j = m - 1;
            while (j >= 0 && pattern.charAt(j) == text.charAt(i + j)) {
                j--;
            }
            if (j < 0) {
                return i; // 匹配成功，返回匹配位置
            } else {
                i += Math.max(goodSuffix[j + 1], j - badCharShift[text.charAt(i + j)]);
            }
        }
        return -1; // 未匹配成功，返回-1
    }

    public static void main(String[] args) {
        BoyerMoore bm = new BoyerMoore();
        String text = "This is a test";
        String pattern = "test";
        bm.preProcessPattern(pattern);
        int index = bm.search(text, pattern);
        if (index != -1) {
            System.out.println("Pattern found at index: " + index);
        } else {
            System.out.println("Pattern not found");
        }
    }
}

Zusammenfassung:
In diesem Artikel wird die Verwendung der Java-Sprache zur Implementierung des Boyer-Moore-Algorithmus vorgestellt und die Verwendung des Algorithmus anhand spezifischer Codebeispiele demonstriert. Der Boyer-Moore-Algorithmus weist eine hohe Effizienz und breite Anwendung im Bereich des String-Matchings auf. Durch die sinnvolle Nutzung von Regeln für gute Suffixe und schlechte Zeichen kann die Effizienz des String-Matchings erheblich verbessert werden. Ich hoffe, dass dieser Artikel Ihnen hilft, den Boyer-Moore-Algorithmus zu verstehen und zu üben.

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