【Python】文字列を繰り返して別の文字列を作れるか判定する方法

2つの文字列 s と t が与えられたとします。このとき、s を何回連結すると t と同じ文字列を作れるかを求めます。s の繰り返しでは t を生成できない場合は -1 を返します。

例えば、入力が s = "tom"、t = "tomtomtom" の場合、「tom」を3回連結すれば「tomtomtom」になるため、出力は 3 となります。

解法のアプローチ

この問題は以下の手順で解くことができます。

• t の長さが s の長さで割り切れない場合は、-1 を返す
• cnt に「t の長さ ÷ s の長さ」の商を代入する
• s を cnt 回繰り返して新しい文字列を作る
• その結果が t と一致する場合は cnt を返す
• 一致しない場合は -1 を返す

実装例

それでは、実際のコードを見てみましょう。

def solve(s, t):
    # t の長さが s の長さで割り切れないかチェック
    if(len(t) % len(s) != 0):
        return -1
    
    # 繰り返し回数を計算
    cnt = int(len(t) / len(s))
    
    # s を cnt 回繰り返す
    s = s * cnt
    
    # 結果が t と一致するか確認
    if(s == t):
        return cnt
    return -1

s = "tom"
t = "tomtomtom"
print(solve(s, t))

入力

"tom", "tomtomtom"

出力

3

コードのポイント

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

• 事前チェックによる高速化： 長さの割り算で割り切れない場合、その時点で -1 を返せるため、無駄な処理を省けます。
• シンプルな比較： Python の文字列乗算（s * cnt）を使うことで、繰り返し処理を1行で簡潔に書けます。

計算量は O(n)（n は文字列 t の長さ）となり、非常に効率的です。