リピート文字列の一致

Question

私はleetcode.comのコンテスト52を行いましたが、私は解決策を理解することができませんでした。

2つの文字列AとBが与えられた場合、Aが繰り返される必要がある最小回数を見つけ、Bがその部分文字列であるようにします。そのような解決策がない場合は、-1を返します。 A = "ABCD" とB =付き例えば

「（abcdabcdabcd 『）、Bはそれの>サブストリングであるcdabcdab

戻り3、三回繰り返してからである。』と、BではありませんAのサブストリングが2回 （ "たとえばABCDABCD"）を繰り返し

溶液である：。

def repeatedStringMatch(self, A, B): 
     """ 
     :type A: str 
     :type B: str 
     :rtype: int 
     """ 
     times = int(math.ceil(float(len(B))/len(A))) 
     for i in range(2): 
     if B in (A * (times + i)): 
      return times + i 
     return -1 

共同研究者のいずれかから、説明は以下のとおりであった：

Aは少なくとも> B（またはもう1つ）以上の長さになるように十分な時間を繰り返さなければならないため、理論的な下限>は長さB /長さA.

xを理論上の下限とすると、ceil（len（B）/ len（A））です。

答えNのみxまたはX + 1

することができ、私は理由を理解していないnは、誰かが助けることができるだけで、xまたはX + 1になることができますか？

Answer 1

x+1 < nの場合とBがn回Aのサブ繰り返され、あなたはB（nは最小ではないことを意味する）または他のスタートを押すことなくAの最後のコピーを切り落とすするか、それにBを埋め込みましたAのBの最初のコピーの終了後ですので、最初のコピーを切り捨てることができます（そしてnは最小ではありません）。

したがって、まったく適合する場合は、x+1コピーに収まる必要があります。長さだけでは< xコピーに収まりません。したがって、残りの可能性はxとx+1です。 （それぞれの答えがどこにあるかの例が見つかります）