Pythonでアナグラム部分文字列を検索する方法【スライディングウィンドウで実装】

はじめに

本記事では、「テキスト中からパターンとそのアナグラム（文字の並べ替え）をすべて検索する」という問題を、Pythonで解く方法を解説します。

問題の定義

問題文： テキストとパターンが与えられます。このとき、テキスト内に出現するパターン本体だけでなく、その並べ替え（アナグラム）すべての出現位置を出力してください。

たとえば、パターンが「TOR」であれば、「ROT」「OTR」「RTO」なども同じ文字構成を持つため、すべて検索対象となります。

アルゴリズムのポイント

この問題はスライディングウィンドウ（滑動窓）の考え方を使うと効率的に解けます。手順は以下のとおりです。

1. パターンの各文字の出現回数を数え、配列 countP に格納する。
2. テキストの先頭からパターンと同じ長さのウィンドウを切り、その文字出現回数を配列 countTW に格納する。
3. ウィンドウを1文字ずつ右へずらしながら、右端に入ってくる文字を加算し、左端から出ていく文字を減算して更新する。
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("Found at Index", (i-M))
        # ウィンドウに新しい文字を追加
        countTW[ord(txt[i])] += 1
        # ウィンドウから左端の文字を削除
        countTW[ord(txt[i-M])] -= 1

    # 最後のウィンドウをチェック
    if compare(countP, countTW):
        print("It is Found at Index : ", N-M)

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

実行結果

Found at Index 2

テキスト「TUTORIALSPOINT」において、インデックス2から始まる3文字「TOR」がパターン「TOR」と一致したため、この位置が出力されました。すべての変数はローカルスコープで宣言されており、処理の流れの中でそれぞれの役割を果たしています。

計算量について

上記の実装では、ウィンドウごとに長さ MAX＝300 の配列全体を比較するため、時間計算量は O((N−M+1) × MAX) となります。扱う文字種が限られている場合は十分実用的ですが、さらに高速化したい場合は、カウントの差分（不一致文字数）だけを管理する手法を採用するとよいでしょう。

まとめ

本記事では、Pythonでアナグラム部分文字列検索を行うプログラムの実装方法を学びました。スライディングウィンドウと文字カウント配列を組み合わせることで、パターンとその並べ替えをすべて効率的に検索できます。文字列検索の基礎的なアルゴリズムとして、ぜひ理解を深めてください。