Pythonで文字列に含まれる回文部分文字列の数を求める方法

すべて小文字（ASCII文字）からなる文字列が与えられたとき、その文字列に含まれる連続する回文部分文字列をすべて見つけ、その総数を求めることを考えます。

たとえば、入力が「level」の場合、出力は 7 になります。「level」「eve」「l」「e」「v」「e」「l」の7つの部分文字列が回文として該当するためです。

解決のための手順

この問題は、次の手順に従って解くことができます。

• N := 26（英小文字の種類数）とする
• n := 文字列 str の長さとする
• sum := 0 として初期化する
• my_map := サイズ N のリストを作成し、すべての要素を 0 で初期化する
• i を 0 から n-1 まで繰り返す
  • my_map[ord(str[i]) - ord('a')] の値を 1 増やす（各文字の出現回数をカウント）
• i を 0 から N-1 まで繰り返す
  • my_map[i] が 0 以外の場合、sum に my_map[i] × (my_map[i] + 1) ÷ 2 を加算する
• sum を返す

考え方のポイント

ある文字が文字列中に c 回出現するとき、その文字から作られる部分文字列の組み合わせは c × (c + 1) ÷ 2 通りになります。これは「c個の中から2つを選ぶ（重複可）」組み合わせの計算式です。この値を26種類の文字すべてについて合計することで、回文部分文字列の総数を効率よく求めることができます。

実装例

以下のPythonコードを見ると、処理の流れがより理解しやすくなります。

N = 26

def all_palindrome_substr_count(s):
    n = len(s)
    total = 0
    my_map = [0] * N
    for i in range(n):
        my_map[ord(s[i]) - ord('a')] += 1
    for i in range(N):
        if my_map[i]:
            total += (my_map[i] * (my_map[i] + 1) // 2)
    return total

s = "level"
print(all_palindrome_substr_count(s))

入力

"level"

出力

7