Pythonで文字列内にアナグラムが存在するすべての部分文字列を検索するプログラム

小文字のみで構成された文字列 s が与えられます。ここで求めたいのは、文字列内の別の場所に、その部分文字列のアナグラム（文字を並べ替えたもの）が必ず存在するような部分文字列をすべて見つけ、辞書順（辞書式順序）にソートしたリストとして返すことです。

たとえば、入力が s = "abcba" の場合、出力は以下のようになります。

['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba', 'bc', 'bcba', 'cb', 'cba']

これらの各部分文字列について、元の文字列内の異なる位置に対応するアナグラムが実際に存在することを確認できます。なお、同じ文字（たとえば 'a'）が複数回現れるのは、出現位置ごとに個別にカウントしているためです。

解法の考え方

ポイントは、「2つの文字列がアナグラムの関係にある ⇔ 文字をソートすると一致する」という性質です。この性質を利用して、同じキーを持つ部分文字列同士をグループ化していきます。具体的には、次の手順に従います。

• res := 結果を格納するための新しいリスト

• L := 文字列 s の長さ

• i を 1 から L まで繰り返す（取り出す部分文字列の長さ）

  • smap := 値がリスト型である空の辞書（defaultdict）を用意

  • j を 0 から L − i まで繰り返す（部分文字列の開始位置）

    • cs := s のインデックス j から j + i − 1 までの部分文字列

    • k := cs の文字をソートして連結した文字列（アナグラム判定用の正規形キー）

    • cs を smap[k] の末尾に追加

  • smap 内の各キー k と値 v について

    • v の要素数が 2 以上であれば、v の要素をすべて res に追加

• res をソートして返す

実装例

以下のPythonコードを見ると、処理の流れがより明確になります。

from collections import defaultdict

def solve(s):
    res = []
    L = len(s)
    for i in range(1, L + 1):
        smap = defaultdict(list)
        for j in range(L - i + 1):
            cs = s[j : j + i]
            k = "".join(sorted(cs))
            smap[k].append(cs)
        for k, v in smap.items():
            if len(v) >= 2:
                res.extend(v)

    return sorted(res)

s = "abcba"
print(solve(s))

入力

"abcba"

出力

['a', 'a', 'ab', 'abc', 'abcb', 'b', 'b', 'ba', 'bc', 'bcba', 'cb', 'cba']

計算量の目安

この方法では、考えられるすべての長さ・開始位置の組み合わせについて部分文字列を生成し、それぞれをソートしてキーを作るため、時間計算量はおおよそ O(n³ log n) になります（n は文字列の長さ）。シンプルな全探索的なアプローチですが、ロジックが分かりやすく、中程度の長さの文字列であれば十分に実用的です。より大きな入力を扱う場合は、ローリングハッシュなどでキー計算を高速化する工夫も有効です。