Javaを使用してBoyer-Mooreアルゴリズムを実装する方法

Java を使用して Boyer-Moore アルゴリズムを実装する方法

はじめに:
コンピューター サイエンスでは、文字列のマッチングは一般的なタスクです。文字列照合アルゴリズムがこの問題を解決する鍵となります。効率的な文字列マッチング アルゴリズムの 1 つは、Boyer-Moore アルゴリズムです。この記事では、Java 言語を使用してこのアルゴリズムを実装する方法を紹介し、具体的なコード例を添付します。

Boyer-Moore アルゴリズムの原理:
Boyer-Moore アルゴリズムは、マルチパターン文字列マッチング アルゴリズムであり、パターン文字列を前処理し、適切な接尾辞ルールと不適切な文字ルールを組み合わせることでマッチングを完了します。中心的な考え方は、パターン文字列と照合対象の文字列との間の照合プロセス中に、一致しない文字をできる限りスキップし、それによって照合効率を向上させることです。

具体的な実装手順:

1. パターン文字列の前処理:
   まず、パターン文字列を前処理し、2 つの配列 (不良文字配列と素敵なサフィックス配列) を生成する必要があります。 。

   • 不正な文字配列: パターン文字列内の各文字の右端の位置を格納します。
   • 良好なサフィックス配列: パターン文字列内のパターン文字列のサフィックス部分文字列の右端の出現位置を記録し、この部分文字列がパターン文字列のプレフィックスと一致するかどうかを記録します。

2. マッチング プロセス:
   マッチング プロセスでは、マッチングする文字列の末尾から順にマッチングを開始します。

   • まず、パターン文字列の末尾と照合対象の文字列の末尾を合わせて照合してみます。
   • マッチングが成功した場合は、マッチングの開始位置を返します。そうでない場合は、不正な文字と良好なサフィックスのルールに従ってパターン文字列の位置を移動して、マッチングを続行します。

具体的なコードは次のとおりです:

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");
        }
    }
}

概要:
この記事では、Java 言語を使用して Boyer-Moore アルゴリズムを実装する方法を紹介します。特定のコード例を通じて、アルゴリズムの使用法を示します。 Boyer-Moore アルゴリズムは効率が高く、文字列マッチングの分野で広く応用されており、良いサフィックスと悪い文字ルールを合理的に利用することで、文字列マッチングの効率を大幅に向上させることができます。この記事が、Boyer-Moore アルゴリズムの理解と実践に役立つことを願っています。

以上がJavaを使用してBoyer-Mooreアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。