Javaで実装するアナグラム部分文字列検索アルゴリズム

アナグラム部分文字列検索とは、テキスト（対象文字列）の中から、指定したパターンを並べ替えた文字列（アナグラム）と一致する部分文字列をすべて見つけるアルゴリズムです。本記事では、Javaによる具体的な実装例を、サンプルコード・実行結果・動作解説とともに紹介します。

サンプルコード

public class Demo{
    static final int max_val = 256;
    static boolean compare_vals(char my_arr_1[], char my_arr_2[]){
        for (int i = 0; i < max_val; i++)
        if (my_arr_1[i] != my_arr_2[i])
        return false;
        return true;
    }
    static void search_subs(String my_pattern, String my_text){
        int pat_len = my_pattern.length();
        int txt_len = my_text.length();
        char[] count_pat = new char[max_val];
        char[] count_txt = new char[max_val];
        for (int i = 0; i < pat_len; i++){
            (count_pat[my_pattern.charAt(i)])++;
            (count_txt[my_text.charAt(i)])++;
        }
        for (int i = pat_len; i < txt_len; i++){
            if (compare_vals(count_pat, count_txt))
            System.out.println("The element was found at index " + (i - pat_len));
            (count_txt[my_text.charAt(i)])++;
            count_txt[my_text.charAt(i-pat_len)]--;
        }
        if (compare_vals(count_pat, count_txt))
        System.out.println("The element was found at index " + (txt_len - pat_len));
    }
    public static void main(String args[]){
        String my_text = "ABNFGHABNJGH";
        String my_pattern = "NFGH";
        search_subs(my_pattern, my_text);
    }
}

実行結果

The element was found at index 2

この例では、テキスト「ABNFGHABNJGH」の中に、パターン「NFGH」の並べ替え（アナグラム）に一致する部分文字列が存在するため、「インデックス2」の位置で見つかったことが出力されます。

プログラムの仕組み

1. compare_valsメソッド（配列比較）

Demoクラスでは、扱う文字種の上限を表す定数max_val（256）が定義されています。boolean型を返すcompare_valsメソッドは、2つのカウント配列を受け取り、max_valの範囲まで両配列を走査します。対応する要素が1つでも異なればfalseを返し、すべて一致すればtrueを返します。これにより、2つの文字セットが同一かどうか（＝アナグラムかどうか）を判定できます。

2. search_subsメソッド（スライディングウィンドウ検索）

staticメソッドsearch_subsは、検索対象のテキストとパターンを受け取ります。まず最初のループで、パターン全体とテキストの先頭部分（パターンと同じ長さ）について、各文字の出現回数をそれぞれcount_patとcount_txtに記録します。

次に、2つ目のforループでスライディングウィンドウ方式を採用しています。ウィンドウを1文字ずつ右にずらしながら、新しく入ってくる文字のカウントを増やし、外れていく文字のカウントを減らします。各ステップでcompare_valsによりパターン側とテキスト側のカウント配列を比較し、一致していればその開始インデックスを出力します。

3. mainメソッド（実行エントリポイント）

mainメソッドでは、検索対象テキスト「ABNFGHABNJGH」とパターン「NFGH」を定義し、search_subsメソッドを呼び出します。この設計により、全位置で毎回カウントを計算し直すことなく効率的な検索が可能となり、計算量はO(n)程度に抑えられます。