アナグラムパターン検索アルゴリズムの解説とC++実装例

アナグラムとは、ある文字列やパターンに含まれる文字を並べ替えることで作れる、すべての順列のことを指します。通常のパターン検索では、パターンそのものと完全に一致する部分のみを探します。一方、アナグラムパターン検索はこれとは少し異なり、テキスト中に現れる「指定パターンのあらゆる並べ替え」をすべて検索対象とします。

アナグラムパターン検索の基本的な考え方

この問題を解くためには、テキスト全体を「パターンと同じ長さのウィンドウ」に分割して考えます。まず、パターンに含まれる各文字の出現回数を数え、配列に記録します。次に、各ウィンドウについても同じように出現頻度配列を作成し、両方の配列が一致しているかどうかを比較します。両者が一致していれば、その位置にパターンのアナグラムが存在すると判断できます。

アナグラムパターン検索アルゴリズムの時間計算量は O(n) です。これは、各ウィンドウの比較が固定サイズ（26種類の英字）の配列同士の比較であるため、定数時間とみなせるからです。

入力と出力

入力:
メイン文字列 "AABAACBABBCABAABBA"、パターン "AABC"

出力:
Anagram found at position: 2
Anagram found at position: 3
Anagram found at position: 4
Anagram found at position: 10

アルゴリズム

anagramSearch(text, pattern)

入力 −　メイン文字列とパターン

出力 −　パターンおよびそのすべてのアナグラムが見つかった位置の一覧

Begin
    patternFreq 配列と stringFreq 配列を定義する
    patLen := パターンの長さ
    stringLen := テキストの長さ
    patternFreq 配列の全要素を 0 で初期化する

    パターンに含まれるすべての文字に対して、
        出現頻度を 1 増やす
    done

    i := 0 から i <= stringLen - patLen まで繰り返す
        stringFreq の全要素を 0 で初期化する
        各ウィンドウに含まれるすべての文字に対して、
            出現頻度を 1 増やす
        done

        もし stringFreq と patternFreq が一致したならば、
            その位置 i にアナグラムが見つかったとして表示する
    done
End

C++による実装例

#include<iostream>
#include<cstring>
#define LETTER 26
using namespace std;

bool arrayCompare(int *array1, int *array2, int n) {
    for(int i = 0; i<n; i++) {
        if(array1[i] != array2[i])
            return false; // 1つでも不一致があれば処理を中断
    }
    return true; // 両配列は同一
}

void setArray(int *array, int n, int value) {
    for(int i = 0; i<n; i++)
        array[i] = value; // 配列の全要素に値を設定
}

void anagramSearch(string mainString, string patt, int *array, int *index) {
    int strFreq[LETTER], pattFreq[LETTER];
    int patLen = patt.size();
    int stringLen = mainString.size();
    setArray(pattFreq, LETTER, 0);      // すべての頻度を0で初期化

    for(int i = 0; i<patLen; i++) {
        int patIndex = patt[i] - 'A';   // 'A'のASCIIコード値を差し引く
        pattFreq[patIndex]++;           // 頻度を増加
    }

    for(int i = 0; i<=(stringLen - patLen); i++) {  // ウィンドウの移動範囲
        setArray(strFreq, LETTER, 0);       // メイン文字列用の頻度配列を0で初期化
        for(int j = i; j<(i+patLen); j++){  // 各ウィンドウごとの頻度を更新
            int strIndex = mainString[j] - 'A';
            strFreq[strIndex]++;            // 頻度を増加
        }

        if(arrayCompare(strFreq, pattFreq, LETTER)) {  // 両配列が一致した場合
            (*index)++;
            array[*index] = i;              // i番目の位置でアナグラムを発見
        }
    }
}

int main() {
    string mainStrng = "AABAACBABBCABAABBA";
    string pattern = "AABC";
    int matchLocation[mainStrng.size()];
    int index = -1;
    anagramSearch(mainStrng, pattern, matchLocation, &index);

    for(int i = 0; i<=index; i++) {
        cout << "Anagram found at position: " << matchLocation[i] << endl;
    }
}

出力結果

Anagram found at position: 2
Anagram found at position: 3
Anagram found at position: 4
Anagram found at position: 10