Pythonで文字列内のアナグラム（並べ替え語）をすべて検索する方法

このチュートリアルでは、ある単語のアナグラム（同じ文字を並べ替えて作った語）が、別の文字列のどこに出現するかをすべて検索するPythonプログラムを作成します。

まず、具体的な例を見てみましょう。

入力:
anagram = "cat"
string = "tacghactcat"
出力:
Anagram at 0
Anagram at 5
Anagram at 7
Anagram at 8

この例では、「cat」のアナグラム（tac、act、catなど）が元の文字列「tacghactcat」の中に4箇所で見つかり、それぞれの開始インデックスが出力されています。

アルゴリズム

以下の手順に従ってコードを書いていきます。

1. 検索対象の単語と、検索先の文字列の2つを初期化する。
2. 2つの文字列が互いにアナグラムかどうかを判定する関数を作成する。
3. 検索先の文字列を先頭から順に走査する。
   3.1. 手順2で作成した関数を使い、部分文字列がアナグラムかどうかを判定する。
      3.1.1. Trueであれば、その開始インデックスを出力する。

ポイント：collections.Counterの活用

アナグラムの判定には、標準ライブラリのcollections.Counterが便利です。Counterは文字の出現回数を辞書形式でカウントしてくれるため、2つの文字列のCounter同士を比較すれば、構成する文字とその個数が完全に一致しているかどうか、つまりアナグラムかどうかを簡単に判定できます。

コード例

# アナグラムの判定のためにcollectionsをインポート
import collections

# 2つの文字列を初期化
anagram = 'cat'
string = 'tacghactcat'

# アナグラムかどうかを判定する関数
def is_anagram(string):
    # アナグラムの判定
    if collections.Counter(anagram) == collections.Counter(string):
        # アナグラムならTrueを返す
        return True
    else:
        # アナグラムでなければFalseを返す
        return False

# 両方の文字列の長さを取得
anagram_len = len(anagram)
string_len = len(string)

# 文字列を先頭から順に走査
for i in range(string_len - anagram_len + 1):
    # 部分文字列がアナグラムかどうかを判定
    if is_anagram(string[i:i+anagram_len]):
        # 開始インデックスを出力
        print(f'Anagram at {i}')

コードの解説

このプログラムの仕組みは次のとおりです。

• スライディングウィンドウ方式： ループ変数iを0からstring_len - anagram_lenまで動かし、毎回長さが「cat」と同じ3文字の部分文字列string[i:i+anagram_len]を切り出して判定します。範囲の終点を+1しているのは、文字列の末尾まで窓が届くようにするためです。
• 判定処理： is_anagram関数内で、検索語「cat」と切り出した部分文字列それぞれのCounterを生成し、一致するかどうかを比較しています。
• 計算量： この実装の計算量はO(n×m)です（nは検索先の文字列の長さ、mは検索語の長さ）。文字列が非常に長い場合は、ウィンドウを1文字ずつずらしながらCounterを差分更新することで、より高速化できます。

出力

上記のプログラムを実行すると、次のような結果が得られます。

Anagram at 0
Anagram at 5
Anagram at 7
Anagram at 8

期待どおり、「tacghactcat」の中に「cat」のアナグラムが4箇所見つかりました。

まとめ

今回は、collections.Counterとスライディングウィンドウを組み合わせることで、文字列内のすべてのアナグラム位置を効率よく検索する方法を学びました。この手法は、スペルチェックやパズル求解、テキスト解析など、さまざまな場面で応用できます。チュートリアルについて疑問点がある場合は、コメント欄でお気軽にお尋ねください。