【アルゴリズム】文字列探索（Boyer-Moore法）｜基本情報技術者科目B対策

2023年4月から基本情報技術者の試験制度が変更されたものの科目B（旧：午後問題）の重要さは変わりません。

出題方式は「多肢選択式」で以前と同じですが、データ構造及びアルゴリズムが8割、情報セキュリティが2割の割合で出題される点が大きく変わっています。

合格基準点は600点以上/1000点満点中、つまり6割以上取れれば合格になります。

そんな科目Bのデータ構造及びアルゴリズムについて、基本となる探索の問題について考えてみましょう。

文字列探索アルゴリズムとは？？
Boyer-Moore法とは？？
どんなときに使う？
Boyer-Moore法の実装例（プログラム）
まとめ

文字列探索アルゴリズムとは？？

文字列探索（String Searching）は、与えられたテキスト内で特定のパターン（検索対象となる文字列）を検索する処理です。文字列探索は、テキスト処理や文字列マッチングなどの応用で広く使用されます。

＜探索アルゴリズム例＞

・線形探索

・ブルートフォース法

・KMP法

・Boyer-Moore法　　等

上記の方法以外にも、有名な文字列探索アルゴリズムとしては、ラビン-カープ法（Rabin-Karp）、Aho-Corasick法などがあります。適切なアルゴリズムの選択は、テキストとパターンの長さ、探索の頻度、処理速度の要求などによって異なってきます。

Boyer-Moore法とは？？

Boyer-Moore法は、効率的な文字列探索アルゴリズムの一つであり、1977年にRobert S. BoyerとJ Strother Mooreによって提案されました。Boyer-Moore法は、一般的にKMP法よりも高速に動作し、特にパターンが長い場合に優れたパフォーマンスを発揮します。

Boyer-Moore法の特徴は、パターンの末尾から比較を開始し、一致しない場合にどれだけスキップするかを決定する「バッドチャータブル」および「グッドサフィックスルール」を利用する点です。これにより、一致しなかった場合にスキップする位置を最適化し、不要な比較を減らします。

具体的な手順は以下の通りです：

パターンの末尾から比較を開始します。
テキストの位置を後ろから前に進めながら、パターンの文字とテキストの文字を比較します。
- 一致する場合：比較を続行します。
- 一致しない場合：
  - バッドチャータブルに基づいて、一致しなかった文字がパターン内のどの位置に存在するかを調べます。パターン内に存在しない場合は、パターンの長さ分だけスキップします。
  - グッドサフィックスルールを利用して、一致しなかった位置より前の部分文字列がパターンの中で別の一致を持つかを調べます。一致する場合は、適切な位置にスキップします。
  - 上記のどのルールにも該当しない場合は、パターンの長さ分だけスキップします。
パターンの先頭まで繰り返します。

どんなときに使う？

Boyer-Moore法は、バッドチャータブルとグッドサフィックスルールを利用することで、効率的に不要な比較をスキップすることができます。これにより、一致しなかった場合のスキップ量を最適化し、高速な探索を実現します。

Boyer-Moore法は実装がやや複雑であり、KMP法よりも理解が難しいかもしれませんが、一般的には高速な文字列探索に使用されるアルゴリズムです。

Boyer-Moore法の実装例（プログラム）

実装例は下記です。

Web上で実際にプログラムを動かすことができるサイトがあります。

色々プログラムをいじってみましょう！

Online PHP/Java/C++... editor and compiler | paiza.IO

このプログラムは、与えられたテキスト内で指定されたパターンを検索し、一致した場合にその位置を表示します。

＜実装例＞

public class Main {
    public static int boyerMooreSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        
        int[] badChar = new int[256]; // バッドチャータブル

        // バッドチャータブルを初期化
        for (int i = 0; i < 256; i++) {
            badChar[i] = -1;
        }

        // パターン中の文字の最後の出現位置を記録
        for (int i = 0; i < m; i++) {
            badChar[(int) pattern.charAt(i)] = i;
        }

        int shift = 0; // スキップする量

        while (shift <= n - m) {
            int j = m - 1;

            // パターンを後ろから比較していく
            while (j >= 0 && pattern.charAt(j) == text.charAt(shift + j)) {
                j--;
            }

            if (j < 0) {
                return shift; // パターンが見つかった場合、位置を返す
            } else {
                int badCharShift = j - badChar[text.charAt(shift + j)];
                int goodSuffixShift = 0;

                // グッドサフィックスルールを適用してスキップする量を計算
                if (j < m - 1) {
                    goodSuffixShift = getGoodSuffixShift(j, m, pattern);
                }

                shift += Math.max(badCharShift, goodSuffixShift);
            }
        }

        return -1; // パターンが見つからなかった場合、-1を返す
    }

    private static int getGoodSuffixShift(int j, int m, String pattern) {
        int shift = 0;
        int k = m - j - 1;

        // パターンの一致する接尾辞を探す
        for (int i = j + 1; i < m; i++) {
            if (pattern.substring(0, i).endsWith(pattern.substring(j + 1))) {
                shift = k;
            }
            k--;
        }

        return shift;
    }

    public static void main(String[] args) {
        String text = "ABCABCABDABC";
        String pattern = "ABCABD";

        int result = boyerMooreSearch(text, pattern);

        if (result == -1) {
            System.out.println("パターンが見つかりませんでした");
        } else {
            System.out.println("パターンが見つかった位置: " + result);
        }
    }
}