Pythonで文字列内の最大k回繰り返し部分文字列(k-repeating)を見つける方法

問題の概要

文字列 s が与えられたとき、文字列 w を k 回連結した結果が s の部分文字列になる場合、w は「k-repeating(繰り返し)文字列」であると言います。そして、w の最大 k-repeating 値とは、その条件を満たす最大の k のことです。もし w が s の部分文字列として一度も現れない場合は、最大 k-repeating 値は 0 になります。

例えば、s = "papaya"、w = "pa" の場合、"pa" は "papaya" の中に2回現れるため、答えは 2 となります。

解決のための手順

• s の中に w が出現する回数を数えます
• 出現回数が 0 の場合は、0 を返します
• 出現回数から 1 まで降順にループし、w を i 回繰り返した文字列が s に含まれているかを確認します
• 含まれていれば、その時点の i を返します(これが最大の k になります)

Pythonでの実装例

以下のコードで実際の動作を確認できます。

def solve(s, w):
    Count = s.count(w)
    if Count == 0:
        return 0
    for i in range(Count, 0, -1):
        if w * i in s:
            return i

s = "papaya"
w = "pa"
print(solve(s, w))

入力

"papaya", "pa"

出力

2

コードの解説

このアルゴリズムのポイントは以下の3点です。

• s.count(w): 文字列メソッド count() を使うことで、w が s に何回出現するかを取得できます。この値が探索範囲の上限になります。
• w * i: Pythonでは文字列に整数を掛けると、その文字列を指定回数繰り返した新しい文字列が生成されます。例えば "pa" * 2 は "papa" になります。
• range(Count, 0, -1): 大きい方から小さい方へ降順にループすることで、最初に見つかった値が自動的に最大の k-repeating 値になります。

なお、この手法はシンプルで理解しやすい一方、各候補ごとに部分文字列の一致判定を行うため、文字列が非常に長い場合には計算コストが増える点に注意してください。ただし、日常的な規模の文字列処理では十分に実用的です。