Pythonで文字列の左右をトリミングして作れる回文の数を求めるプログラム

文字列 s が与えられたとき、s の左右をトリミング（切り詰める）ことで得られる回文の個数を求める問題を考えてみましょう。

例えば、入力が s = "momo" の場合、出力は 6 になります。これは「mom」「omo」「m」「m」「o」「o」の6つの回文を作ることができるためです。

この問題を解くために、以下の手順に従います。

• 関数 expand() を定義します。引数として i、j、s を受け取ります。
• カウンタ c := 0 で初期化します。
• i >= 0 かつ j が s の長さ未満 かつ s[i] == s[j] である間、以下を繰り返します。
  • i := i − 1、j := j + 1 とする
  • c := c + 1 とする
• c を返します。
• メイン処理では以下を実行します。
• c := 0 とします。
• i を 0 から s の長さまでループさせます。
  • c := c + expand(i, i, s)
  • c := c + expand(i, i + 1, s)
• c を返します。

アルゴリズムのポイント

この手法は「中心展開（Expand Around Center）」と呼ばれるテクニックを利用しています。文字列内のすべての位置を回文の中心候補として扱い、奇数長の回文（expand(i, i)）と偶数長の回文（expand(i, i+1)）の両方をチェックすることで、存在するすべての回文部分文字列を効率よく数えられます。計算量は O(n²) となり、全ての部分文字列を総当たりで調べる方法に比べて効率的です。

それでは、実際の実装を見ながら理解を深めましょう。

実装例

def expand(i, j, s):
    c = 0
    while i >= 0 and j < len(s) and s[i] == s[j]:
        i -= 1
        j += 1
        c += 1
    return c

class Solution:
    def solve(self, s):
        c = 0
        for i in range(len(s)):
            c += expand(i, i, s)
            c += expand(i, i + 1, s)
        return c

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

入力

"momo"

出力

6