Pythonで文字列に含まれるすべての異なる回文部分文字列を検索する方法

小文字のASCII文字のみで構成された文字列が与えられたとき、その中に含まれるすべての異なる連続する回文部分文字列を見つける問題について解説します。

例えば、入力が "bddaaa" の場合、出力は次のようになります。

[a, aa, aaa, b, d, dd]

アルゴリズムの考え方

この問題は、Manacher法を応用した手法を使うことで効率的に解くことができます。基本的なアイデアは、偶数長と奇数長の両方の回文を一度に扱うために、文字列の前後に異なる番兵文字（@ と #）を追加し、各位置における回文半径を行列に記録していくというものです。

具体的な手順は以下の通りです。

• 結果を格納するための辞書 m を用意します。
• n に文字列 s の長さを代入します。
• matrix として、n+1 列 × 2 行の 0 で初期化された二次元配列を作成します。1 行目は奇数長の回文、2 行目は偶数長の回文に対応します。
• 文字列 s の先頭に @、末尾に # を連結します。
• j = 0 ～ 1 の各ループについて、次の処理を行います。
  • 変数 temp を 0 で初期化し、i を 1 から開始します。
  • s[i - temp - 1] と s[i + j + temp] が一致する限り temp を増加させ、回文の半径を求めます。
  • 求めた値を matrix[j][i] に記録した後、すでに計算済みの情報を利用して、後続の位置の値を効率的に埋めていきます。
• 処理終了後、番兵文字を取り除き、各位置の回文半径をもとに、実際の部分文字列を辞書 m に登録していきます。辞書を使うことで、重複する回文は自動的に除外されます。
• 最後に、辞書に含まれるすべての回文部分文字列を表示します。

実装例

それでは、実際のPythonコードを見てみましょう。

def find_substr(s):
    m = dict()
    n = len(s)
    matrix = [[0 for x in range(n+1)] for x in range(2)]
    s = "@" + s + "#"
    for j in range(2):
        temp = 0
        matrix[j][0] = 0
        i = 1
        while i <= n:
            while s[i - temp - 1] == s[i + j + temp]:
                temp += 1
            matrix[j][i] = temp
            k = 1
            while (matrix[j][i - k] != temp - k) and (k < temp):
                matrix[j][i+k] = min(matrix[j][i-k], temp - k)
                k += 1
            temp = max(temp - k, 0)
            i += k
    s = s[1:len(s)-1]
    m[s[0]] = 1
    for i in range(1,n):
        for j in range(2):
            for temp in range(matrix[j][i],0,-1):
                m[s[i - temp - 1 : i - temp - 1 + 2 * temp + j]] = 1
        m[s[i]] = 1
    for i in m:
        print(i)

find_substr("bddaaa")

入力

bddaaa

出力

a
aa
b
aaa
d
dd

まとめ

このアルゴリズムでは、Manacher法の仕組みを応用することで、全ての部分文字列を総当たりで調べる O(n³) のアプローチよりもはるかに高速な O(n) の計算量で回文部分文字列を検出できます。また、結果の管理に辞書を使用しているため、重複する回文が自動的に排除され、「異なる」回文だけが出力される点もポイントです。