Javaを使用して文字列マッチングアルゴリズムを実装する方法

Java を使用して文字列マッチング アルゴリズムを実装する方法

はじめに:
文字列マッチング アルゴリズムはコンピュータ分野でよくある問題であり、メイン文字列のマッチングに使用されます。特定のパターン文字列の出現を検索します。実際の開発では、テキストエディタの検索機能や検索エンジンのキーワードマッチングなど、文字列のマッチングが必要になることがよくあります。この記事では、いくつかの一般的な文字列一致アルゴリズムを紹介し、対応する Java コード例を示します。

1. ブルート フォース マッチング アルゴリズム
ブルート フォース マッチング アルゴリズムは、単純マッチング アルゴリズムとも呼ばれ、最も基本的な文字列マッチング アルゴリズムです。その原理は非常に単純です。つまり、メイン文字列のすべての位置から開始して、一致しない文字が現れるか一致が見つかるまで、文字ごとにパターン文字列と比較します。

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

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 アルゴリズム
KMP アルゴリズムは、パターン文字列のマッチング情報の一部を使用して、効率的な文字列マッチング アルゴリズムです。不一致を避ける必要がある文字の比較。 KMP アルゴリズムの核心は、パターン文字列の各位置で最も長い共通サフィックスの長さを記録する次の配列を構築することです。

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

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 アルゴリズム
Boyer-Moore アルゴリズムは、パターン文字列内の文字分布情報を使用する効率的な文字列マッチング アルゴリズムです。そしてムーブバックルール。

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

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

結論:
上記は、ブルート フォース マッチング アルゴリズム、KMP アルゴリズム、および Boyer という 3 つの一般的な文字列マッチング アルゴリズムのコード例です。ムーアアルゴリズム。実際のアプリケーションでは、マッチング効率を向上させるために、特定のニーズに応じて適切なアルゴリズムを選択できます。

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