【アルゴリズム】文字列探索（ブルートフォース法）｜基本情報技術者科目B対策

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

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

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

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

文字列探索アルゴリズムとは？？
ブルートフォース法とは？？
どんなときに使う？
ブルートフォース法の実装例（プログラム）
まとめ

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

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

＜探索アルゴリズム例＞

・線形探索

・ブルートフォース法

・KMP法

・Boyer-Moore法　　等

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

ブルートフォース法とは？？

ブルートフォース法（Brute Force）は、文字列探索の一つの手法であり、パターン（検索対象となる文字列）をテキスト内のすべての位置で順番に比較して一致を探す方法です。単純明快な手法であり、実装が比較的簡単ですが、効率は低いという特徴があります。

ブルートフォース法の基本的な手順は以下の通りです：

テキストの最初の位置から始めます。
テキストの現在の位置からパターンの長さだけの部分文字列を切り出します。
切り出した部分文字列とパターンを比較します。
- 一致しない場合：テキストの位置を1つ進めて再度比較します。
- 一致する場合：パターンが見つかったとして処理を終了します。
テキストの終端まで繰り返します。

どんなときに使う？

ブルートフォース法は直感的な手法であり、どのような文字列でも使用できます。しかし、パターンとテキストの長さが増えると効率が低下し、計算時間が増えるという欠点があります。特に、テキスト内に長いパターンが存在する場合には、総当たり的な比較が行われるため、非常に遅くなる可能性があります。

そのため、大規模なテキストや高速な文字列探索を必要とする場合には、ブルートフォース法以外の高速な探索アルゴリズム（例えば、ボイア-ムーア法やクヌース-モリス-プラット法など）を検討することが重要です。

ブルートフォース法の実装例（プログラム）

実装例は下記です。

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

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

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

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

＜実装例＞

public class Main {
    public static int bruteForceSearch(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; // パターンが見つからなかった場合、-1を返す
    }

    public static void main(String[] args) {
        String text = "Hello,world!";
        String pattern = "world";

        int result = bruteForceSearch(text, pattern);

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