Pythonで文字列が同じパターンの繰り返しかどうかを判定する方法

ある文字列が与えられたとき、それが繰り返し文字列（同じ部分文字列が2回以上連なって全体を構成している文字列）であるかどうかを判定する問題を考えてみましょう。

例えば、入力が "helloworldhelloworld" の場合、「helloworld」が2回繰り返された文字列なので、出力は True となります。

解法のアプローチ：約数に注目する

この問題を効率よく解くカギは約数です。文字列の長さを n とするとき、繰り返しの単位となる部分文字列の長さ i は必ず n の約数になります。つまり、n の約数だけを候補として調べれば十分だということです。

具体的な手順は以下の通りです。

1. n を文字列 s の長さとします。
2. 引数 n を受け取る関数 findFactors() を定義します。1から√nまで順番に確認し、n を割り切れる値 i とその商 n / i を両方とも集合 f に追加することで、n の約数をすべて求めて返します。
3. メイン処理では、fact = findFactors(n) で約数の一覧を取得します。
4. 各約数 i について以下をチェックします（i が n そのものの場合は繰り返しにならないためスキップします）。
   • ss := s の先頭から i 文字分の部分文字列
   • val := s の中に ss が出現する回数
   • val が n / i の商と一致すれば True を返します
5. すべての候補で条件を満たさなければ False を返します。

なぜこれで正しく判定できるのか

s.count(ss) がちょうど n / i 回になるということは、部分文字列 ss が隙間なく n / i 回並んで文字列全体を覆っていることを意味します。途中に別の文字が挟まっていれば出現回数は減るため、一致した時点で「繰り返し文字列」と確定できるのです。

Pythonによる実装例

class Solution:
   def solve(self, s):
      n = len(s)

      def findFactors(n):
         f = set()
         i = 1
         while i * i <= n:
            if n % i == 0:
               f.add(int(n / i))
               f.add(i)
            i += 1
         return f

      fact = findFactors(n)
      for i in fact:
         if i == n:
            continue
         ss = s[:i]
         val = s.count(ss)
         if val == int(n / i):
            return True
      return False


ob = Solution()
print(ob.solve("helloworldhelloworld"))

入力

"helloworldhelloworld"

出力

True

計算量について

約数の列挙には O(√n)、各候補ごとの出現回数のカウントには O(n) かかるため、全体の計算量は O(√n × n) 程度になります。文字列長がそれほど大きくなければ、十分実用的な速度で動作します。

おまけ：もっとシンプルな1行テクニック

文字列を2倍につなげた中で元の文字列を検索する定番テクニックを使うと、わずか1行で判定できます。

def solve(s):
    return (s + s).find(s, 1) != len(s)

これは「s が繰り返し文字列ならば、s + s の中に s がインデックス1以降かつ末尾より前の位置で見つかる」という性質を利用したものです。技術面接や競技プログラミングでもよく登場する手法なので、覚えておくと便利でしょう。