Pythonでアナグラム部分文字列検索プログラムを作成する方法

はじめに

この記事では、以下の問題文に対する解決策について学びます。

問題文 − テキストとパターンが与えられたとき、テキスト内に含まれるパターンおよびその順列(アナグラム)の出現位置をすべて出力します。

例えば、テキストが「TUTORIALSPOINT」、パターンが「TOR」であれば、「ROT」や「OTR」といった並べ替えも検索対象となります。

アルゴリズムの考え方

この問題は、スライディングウィンドウ(滑動窓)と文字カウント配列を組み合わせることで効率的に解くことができます。手順は以下のとおりです。

1. パターン内の各文字の出現回数を、カウント配列 countP に記録します。
2. テキストの先頭から、パターンと同じ長さのウィンドウ内の文字出現回数を、カウント配列 countTW に記録します。
3. ウィンドウを1文字ずつ右へずらしながら、新しく入ってくる文字を countTW に加算し、外れていく文字を減算します。
4. countP と countTW が一致したタイミングでは、その位置にパターンのアナグラムが存在することを意味します。

実装例

# 最大値
MAX = 300

# 2つのカウント配列を比較する関数
def compare(arr1, arr2):
    for i in range(MAX):
        if arr1[i] != arr2[i]:
            return False
    return True

# アナグラム検索を行う関数
def search(pat, txt):
    M = len(pat)
    N = len(txt)
    # countP: パターンの文字出現数
    # countTW: テキストの現在のウィンドウ内の文字出現数
    countP = [0] * MAX
    countTW = [0] * MAX
    for i in range(M):
        countP[ord(pat[i])] += 1
        countTW[ord(txt[i])] += 1
    # ウィンドウを1文字ずつずらしながら走査
    for i in range(M, N):
        # 現在のウィンドウとパターンの文字数を比較
        if compare(countP, countTW):
            print("見つかったインデックス:", (i - M))
        # ウィンドウに新しい文字を追加
        countTW[ord(txt[i])] += 1
        # ウィンドウから先頭の文字を削除
        countTW[ord(txt[i - M])] -= 1
    # 最後のウィンドウをチェック
    if compare(countP, countTW):
        print("見つかったインデックス:", (N - M))

# メイン処理
txt = "TUTORIALSPOINT"
pat = "TOR"
search(pat, txt)

出力

見つかったインデックス: 2

すべての変数はローカルスコープで宣言されており、その参照関係は上の図のとおりです。

まとめ

この記事では、文字カウント配列とスライディングウィンドウを活用し、テキスト内に含まれるパターンとそのアナグラム(順列)をすべて検出するPythonプログラムの作成方法について学びました。この手法を用いれば、すべての並べ替えを生成して総当たりで探すよりもはるかに効率的にアナグラム検索が行えます。