Pythonで文字列内の回文ボーダー（回文境界）を検出するプログラム

問題の概要

ある文字列 str が与えられているとします。文字列における「ボーダー（境界）」とは、その文字列の真の接頭辞かつ接尾辞となっている部分文字列のことを指します。たとえば、「ab」は文字列「ababab」のボーダーです。さらに、このボーダー自体が回文である場合、それを「回文ボーダー」と呼びます。

ここで、与えられた文字列 str に含まれる回文ボーダーの個数を f(str) と定義します。求めたいのは、str のすべての空でない部分文字列 str_k に対する f(str_k) の総和です。この合計値は非常に大きくなる可能性があるため、10⁹ + 7 で剰余を取って計算します。

具体例

入力が str = 'pqpqp' の場合、出力は 5 になります。

文字列 'pqpqp' には全部で 15 個の部分文字列が存在しますが、そのうち回文ボーダーを持つのは次の 4 つだけです。

pqp   : f(pqp)   = 1
pqpqp : f(pqpqp) = 2
qpq   : f(qpq)   = 1
pqp   : f(pqp)   = 1

したがって、これらの値の合計は 1 + 2 + 1 + 1 = 5 となります。

解決のためのアルゴリズム

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

ステップ1：palindrome_calculator() 関数の定義

• 引数として input_dict を受け取ります。
• ans を 0 で初期化します。
• input_dict の各要素（item1, item2）に対して、ans に「item2 × (item2 − 1) / 2 の切り捨て値」を加算します。
• ans を返します。

ステップ2：str_check() 関数の定義

• 引数として文字列を受け取ります。
• t_str を文字列の先頭文字とし、すべての文字が t_str と一致するかどうかを確認します。
• 一致しない文字があれば False を、すべて一致していれば True を返します。

ステップ3：string_res() 関数の定義

• i を 2 から文字列長までループし、ans に「i × (i − 1) / 2 の切り捨て値」を加算します。
• 毎回 1000000007 で剰余を取り、最後に ans を返します。

ステップ4：メインロジック

• str_check(string) が True の場合（すべて同じ文字から成る場合）、string_res(string) を返します。
• ans を 0 で初期化し、奇数長用の odd_list（リスト・マップ・カウンタ）を用意します。
• 各文字の出現位置と出現回数を記録し、palindrome_calculator() で奇数長の寄与分を ans に加算します。
• 同様に、隣り合う文字が等しい偶数長用の even_list を構築し、寄与分を加算します。
• 長さ 3 以降の部分文字列について、val が偶数なら even_list、奇数なら odd_list をベースに、両端を 1 文字ずつ拡張できるかを判定しながら新しいリスト new_t を作成します。
• 各段階で palindrome_calculator() の結果を ans に加算し、1000000007 で剰余を取ります。
• 最終的な ans を返します。

Pythonによる実装例

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

def palindrome_calculator(input_dict):
    ans = 0
    for item1, item2 in input_dict.items():
        ans += item2 * (item2 - 1) // 2
    return ans

def str_check(string):
    t_str = string[0]
    for s in string:
        if s != t_str:
            return False
    return True

def string_res(string):
    ans = 0
    for i in range(2, len(string) + 1):
        ans += i * (i - 1) // 2
        ans %= 1000000007
    return ans

def solve(string):
    if str_check(string):
        return string_res(string)
    ans = 0
    odd_list = [[], {}, 1]
    for s in string:
        if s not in odd_list[1]:
            odd_list[1][s] = 0
        odd_list[1][s] += 1
    for i in range(len(string)):
        odd_list[0].append(i)
    ans += palindrome_calculator(odd_list[1])
    even_list = [[], {}, 1]
    for i in range(len(string) - 1):
        if string[i] == string[i + 1]:
            even_list[0].append(i)
            tmp = string[i:i + 2]
            if tmp not in even_list[1]:
                even_list[1][tmp] = 0
            even_list[1][tmp] += 1
    ans += palindrome_calculator(even_list[1])
    for val in range(3, len(string)):
        if val % 2 == 0:
            wt = even_list
        else:
            wt = odd_list
        new_t = [[], {}, val]
        for index in wt[0]:
            if index - 1 >= 0 and index + val - 2 < len(string) and string[index - 1] == string[index + val - 2]:
                new_t[0].append(index - 1)
                tmp = string[index - 1 : index - 1 + val]
                if tmp not in new_t[1]:
                    new_t[1][tmp] = 0
                new_t[1][tmp] += 1
        ans += palindrome_calculator(new_t[1])
        ans %= 1000000007
        if val % 2 == 0:
            even_list = new_t
        else:
            odd_list = new_t
    return ans

print(solve('pqpqp'))

入力

'pqpqp'

出力

5