Pythonで文字列内のすべての回文部分文字列を検出する方法(その2)

ある文字列が与えられたとき、その文字列に含まれるすべての回文部分文字列を抽出することを考えます。ここで重要なのは、同じ並びの部分文字列でも、位置が異なれば別々のものとして数えるという点です。たとえば「aa」が2箇所に出現する場合、それらは1つではなく2つの異なる部分文字列として扱います。

例として、入力が「redivider」である場合を考えてみましょう。この場合の出力は次のようになります。

['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider', 'i', 'd', 'e', 'r']

アルゴリズムの考え方

この問題は、中心拡張法(expand around center)の考え方を使うと効率的に解けます。回文は中心を基準に左右対称であるため、文字列中の各位置を「中心」として、そこから左右へ対称に文字を比較しながら範囲を広げていきます。

ポイントは、中心の位置を0.5刻みで進めることです。これにより、以下の2種類の回文を両方カバーできます。

• 奇数長の回文:1文字を中心とする場合(例:「ivi」)
• 偶数長の回文:文字と文字の間を中心とする場合(例:「dd」)

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

• 結果を格納するための空リスト v を用意します
• 中心位置 pos を 0.0 で初期化します
• pos が文字列の長さ未満である間、以下を繰り返します
  • rad := pos − int(pos)(小数部、つまり0か0.5)を計算します
  • (pos + rad) が文字列長未満、(pos − rad) が0以上、かつ s[int(pos − rad)] と s[int(pos + rad)] が等しい間、以下を繰り返します
    • s の int(pos − rad) 番目から int(pos + rad + 1) 番目までの部分文字列を v の末尾に追加します
    • rad を 1 増やします
  • pos に 0.5 を加算します
• v を返します

サンプルコード

理解を深めるために、実際のPython実装を見てみましょう。

def get_all_pal_sub(s):
    v = []
    pos = 0.0
    while pos < len(s):
        rad = pos - int(pos)
        while ((pos + rad) < len(s) and (pos - rad) >= 0 and (s[int(pos - rad)] == s[int(pos + rad)])):
            v.append(s[int(pos - rad): int(pos + rad + 1)])
            rad += 1
        pos += 0.5
    return v

v = get_all_pal_sub("redivider")
print(len(v))
print(v)

入力

"redivider"

出力

13 ['r', 'e', 'd', 'i', 'v', 'ivi', 'divid', 'edivide', 'redivider', 'i', 'd', 'e', 'r']

処理の流れの解説

「redivider」の場合、まず各1文字(r、e、d、i、v)がそれぞれ長さ1の回文として検出されます。続いて中心を「v」や「i」などに設定した際、「ivi」「divid」「edivide」「redivider」というように、対称性が崩れるまで範囲を拡張していきます。最終的に13個の回文部分文字列(重複する文字も位置違いとして別カウント)が得られます。

この手法の時間計算量は最悪ケースで O(n²) となります(nは文字列の長さ)。これは、各中心からの拡張操作が合計で最大 n² 回発生し得るためです。ただし、単純な全ペア比較による総当たり(O(n³))よりも大幅に効率的であり、実装も簡潔なので、面接や競技プログラミングでもよく使われる定番のアプローチです。