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

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

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

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

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

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

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

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

＜探索アルゴリズム例＞

・線形探索

・ブルートフォース法

・KMP法

・Boyer-Moore法　　等

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

KMP法とは？？

KMP法（Knuth-Morris-Pratt法）は、文字列探索の高速なアルゴリズムの一つです。パターン（検索対象となる文字列）が長くなるほど効果が顕著であり、時間計算量がO(n+m)（nはテキストの長さ、mはパターンの長さ）でありながら高速に動作します。

KMP法の特徴は、事前処理によって「失敗関数」を計算し、パターンの再比較を効率的にスキップする点です。以下にKMP法の基本的な手順を示します：

パターンの失敗関数を事前に計算します。失敗関数は、パターンの各位置において、最長の接頭辞（prefix）と接尾辞（suffix）の一致数を示す情報です。これにより、一致しなかった場合にどれだけスキップするかが決定されます。
テキストとパターンの比較を開始します。テキストの最初の位置から順番にパターンを比較します。
一致しない場合、失敗関数を利用してパターンを適切な位置にスキップします。失敗関数の値を利用して、パターンの位置を移動させます。
パターンの最後に到達するか、テキストの終端まで比較を繰り返します。

どんなときに使う？

KMP法の利点は、パターンの失敗関数を事前に計算することで、一致しなかった場合にパターンをスキップできる点です。これにより、テキスト内の不要な比較回数を減らし、効率的に一致を見つけることができます。

KMP法は文字列探索において広く使用されており、テキスト処理や文字列マッチングなどの応用に活用されています。

KMP法の実装例（プログラム）

実装例は下記です。

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

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

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

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

＜実装例＞

public class Main {
    public static int kmpSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        int[] lps = computeLPSArray(pattern);

        int i = 0; // テキスト内の位置
        int j = 0; // パターン内の位置

        while (i < n) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (j == m) {
                    return i - j; // パターンが見つかった場合、位置を返す
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }

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

    private static int[] computeLPSArray(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        int len = 0;
        int i = 1;

        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }

        return lps;
    }

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

        int result = kmpSearch(text, pattern);

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