Pythonで最長のチャンク回文分解の長さを求めるプログラム

この記事では、与えられたテキストに対して「チャンク回文分解」の最大分割数 k を求める問題を、Pythonを使って解く方法を解説します。

問題の定義

あるテキストが与えられたとき、次の条件をすべて満たすような最大の k を求めます。

• 各 a[i] は空文字列（ブランク）ではない
• 連結した文字列 a[1] + a[2] + ... + a[k] が元のテキストと一致する
• 1 ≤ i ≤ k のすべての i について、a[i] = a[k+1-i] が成り立つ（前から i 番目のチャンクと後ろから i 番目のチャンクが同じ）

具体例

たとえば、入力が text = "antaprezatepzapreanta" の場合、出力は 11 になります。これは、次のように11個のチャンクに分割できるためです。

a | nt | a | pre | za | tpe | za | pre | a | nt | a

前半の「a, nt, a, pre, za」と後半の「za, pre, a, nt, a」が対称になっており、中央の「tpe」が残る形になっているのがわかります。

解法のアルゴリズム

この問題は、両端から順に一致する部分を取り除いていく貪欲法（グリーディ法）で解けます。手順は以下の通りです。

1. カウンター counter を 0 で初期化する
2. i := 1、j := テキストの長さ - 1 とする
3. ic := 0、jc := テキストの長さ とする
4. i ≤ j の間、以下を繰り返す
   • text[ic:i]（左側の候補チャンク）と text[j:jc]（右側の候補チャンク）が一致する場合、counter に 2 を加算し、ic := i、jc := j と更新する
5. 各ステップで i を 1 増やし、j を 1 減らす
6. ループ終了後、ic ≠ jc の場合は中央に余ったチャンクが存在するので、counter に 1 を加算する
7. counter を返す

Pythonでの実装例

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

def solve(text):
    counter = 0
    i, j = 1, len(text) - 1
    ic, jc = 0, len(text)

    while i <= j:
        if text[ic:i] == text[j:jc]:
            counter += 2
            ic = i
            jc = j
        i += 1
        j -= 1

    if ic != jc:
        counter += 1

    return counter

text = "antaprezatepzapreanta"
print(solve(text))

入力

antaprezatepzapreanta

出力

11

計算量について

このアルゴリズムでは、ポインタ i と j が互いに近づきながら全文字を走査し、各ステップで部分文字列の比較を行います。最悪の場合、時間計算量は O(n²) となります。ただし、実用上は多くのケースで高速に動作します。

まとめ

チャンク回文分解の問題は、文字列の両端から対称なチャンクを貪欲に切り出していくことで効率的に解くことができます。ポイントは、左右の候補部分文字列が一致したタイミングで境界を確定させ、最後に中央に残った部分を1チャンクとして数える点です。