Pythonで文字列を回文にするために追加すべき最小文字数を求めるプログラム

文字列 s が与えられたとき、末尾に文字を追加して回文にするために必要な最小の追加文字数を求める問題です。

たとえば、入力が s = "mad" の場合、出力は 2 になります。これは、末尾に "am" を追加することで "madam" という回文を作れるためです。

アプローチ：ローリングハッシュで最長の回文接尾辞を見つける

この問題を効率的に解く鍵は、「文字列の末尾側に最も長く続く回文（回文接尾辞）」を見つけることです。s[i:] が回文であれば、先頭から i 文字分を逆順にして末尾に追加するだけで文字列全体を回文にできます。したがって、答えは「s[i:] が回文となる最小の i」と一致します。

すべての接尾辞を毎回 O(n) かけて検査すると非効率なため、ここではローリングハッシュを使用します。順方向のハッシュと逆方向のハッシュを同時に更新し、両者が一致した位置を回文の候補とみなします。ハッシュ衝突の可能性を抑えるため、基数 256・法 10^9 + 7 を採用しています。

アルゴリズムの手順

• 定数 b := 256、m := 10^9 + 7 を設定する
• s を、各文字の ASCII コードから 97 を引いた値（0〜25 の整数）のリストに変換する
• r（逆方向ハッシュ）と l（順方向ハッシュ）を、s の最後の文字で初期化する
• n := 文字列の長さ、res := n − 1（初期答え）、p := b とする
• i を n − 2 から 0 まで 1 ずつ減らしながら以下を繰り返す
  • r := (r + s[i] × p) mod m で逆方向ハッシュを更新する
  • l := (l × b + s[i]) mod m で順方向ハッシュを更新する
  • p := (p × b) mod m で基数の冪を更新する
  • l == r ならば res := i と更新する（より長い回文接尾辞が見つかったことを意味する）
• res を返す

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

実装例

class Solution:
    def solve(self, s):
        b = 256
        m = 10 ** 9 + 7
        s = list(ord(i) - 97 for i in s)
        r = l = s[-1]
        n = len(s)
        res = n - 1
        p = b
        for i in range(n - 2, -1, -1):
            r += s[i] * p
            r %= m
            l *= b
            l += s[i]
            l %= m
            p *= b
            p %= m
            if l == r:
                res = i
        return res

ob = Solution()
s = "mad"
print(ob.solve(s))

入力

"mad"

出力

2

計算量

時間計算量は O(n)、空間計算量は O(n)（文字列を数値リストに変換する分）です。ハッシュ比較により各位置での回文判定をほぼ定数時間で行えるため、全接尾辞を素朴にチェックする O(n²) の手法よりも高速に動作します。