686.重复叠加字符串匹配

原题

一、利用重复的循环性质

记a复制n次为a*n

当len(a*n) < len(b)时，无法匹配。

当len(a*n) <= len(b) < len(a*(n+1))时，若b是a*n 或 a*(n+1)的子串，此时n或n+1就是最少重复次数。

因为若b串与此区间的复制串不匹配，则继续复制也不会匹配。若已匹配，则继续复制仍然匹配（a是循环的）

最后，就是看b串与a的复制串匹配时，a复制了n次还是n+1次

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        dup = ""    #复制串
        n = 0   #复制次数
        while len(dup) < len(b):
            dup += a
            n += 1
        dup += a	#复制n+1次
        idx = str.find(dup, b)	#求匹配下标
        if idx == -1:
            return -1
        else:
            if idx + len(b) > n * len(a):
                return n + 1
            else:
                return n