Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1.


For example, with A = "abcd" and B = "cdabcdab". 


Return 3, because by repeating A three times (“abcdabcdabcd”), B is a substring of it; and B is not a substring of A repeated two times ("abcdabcd").


Note:
The length of A and B will be between 1 and 10000.

Difficulty: introductory

Starter code:

class Solution:
    def repeatedStringMatch(self, a: str, b: str) -> int:
        

Solutions:
class Solution:
     def repeatedStringMatch(self, A, B):
         """
         :type A: str
         :type B: str
         :rtype: int
         """
         
         if not set(B).issubset(set(A)):
             return -1
         
         max_rep = len(B) // len(A) + 3
         A_new = A
         
         for i in range(1,max_rep):
             if B in A_new:
                 return i
             A_new += A
         return -1

class Solution:
     def repeatedStringMatch(self, A, B):
 
         times = 1
         tmp = A
         if (not set(B).issubset(set(A))):
             return -1
         maxTime = math.ceil(len(B) / len(A))
         while True:
             if B in A:
                 break
             elif (times <= maxTime):
                 A += tmp
                 times += 1
             else:
                 return -1
         return times

class Solution:
     def repeatedStringMatch(self, A, B):
         """
         :type A: str
         :type B: str
         :rtype: int
         """
         def check(index):
             return all(A[(i+index) % len(A)] == c
                        for i, c in enumerate(B))
 
         M, p = 10**9+7, 113
         p_inv = pow(p, M-2, M)
         q = (len(B)+len(A)-1) // len(A)
 
         b_hash, power = 0, 1
         for c in B:
             b_hash += power * ord(c)
             b_hash %= M
             power = (power*p) % M
 
         a_hash, power = 0, 1
         for i in range(len(B)):
             a_hash += power * ord(A[i%len(A)])
             a_hash %= M
             power = (power*p) % M
 
         if a_hash == b_hash and check(0): return q
 
         power = (power*p_inv) % M
         for i in range(len(B), (q+1)*len(A)):
             a_hash = (a_hash-ord(A[(i-len(B))%len(A)])) * p_inv
             a_hash += power * ord(A[i%len(A)])
             a_hash %= M
             if a_hash == b_hash and check(i-len(B)+1):
                 return q if i < q*len(A) else q+1
 
         return -1


class Solution(object):
     # Rabin-Karp Algorithm (rolling hash)
     def repeatedStringMatch1(self, A, B):
         """
         :type A: str
         :type B: str
         :rtype: int
         """
         def check(index):
             return all(A[(i+index) % len(A)] == c
                    for i, c in enumerate(B))
 
         M, p = 10**9+7, 113
         p_inv = pow(p, M-2, M)
         q = (len(B)+len(A)-1) // len(A)
 
         b_hash, power = 0, 1
         for c in B:
             b_hash += power * ord(c)
             b_hash %= M
             power = (power*p) % M
 
         a_hash, power = 0, 1
         for i in range(len(B)):
             a_hash += power * ord(A[i%len(A)])
             a_hash %= M
             power = (power*p) % M
 
         if a_hash == b_hash and check(0): return q
 
         power = (power*p_inv) % M
         for i in range(len(B), (q+1)*len(A)):
             a_hash = (a_hash-ord(A[(i-len(B))%len(A)])) * p_inv
             a_hash += power * ord(A[i%len(A)])
             a_hash %= M
             if a_hash == b_hash and check(i-len(B)+1):
                 return q if i < q*len(A) else q+1
 
         return -1
     #KMP
     def repeatedStringMatch(self, A, B):
         """
         :type A: str
         :type B: str
         :rtype: int
         """
  
         def get_fail(s):
             f = [0] * (len(s) + 1)
             for i in range(1, len(s)):
                 j = f[i]
                 while j and s[i] != s[j]: j = f[j]
                 if s[i] == s[j]: j += 1
                 f[i + 1] = j
             return f
  
         # kmp
         f = get_fail(B)
         j = 0
         vis = {0}
         cnt = 1
         while True:
             for i in range(len(A)):
                 while j and A[i] != B[j]: j = f[j]
                 if A[i] == B[j]: j += 1
                 if j == len(B):
                     return cnt
             if j in vis: return -1 
             vis.add(j)
             cnt += 1
         return -1
 
     
     


class Solution:
     def repeatedStringMatch(self, A, B):
         k = int(len(B) / len(A))
         m = ""
         h = A + A[0]
         for i in range(len(B)-1):
             if B[i:i+2] not in h: return -1
         for i in range(k):
             m += A
         while B not in m:
             m += A
             k += 1
             if k>100: return -1
         return k


class Solution:
     def repeatedStringMatch(self, A, B):
         """
         :type A: str
         :type B: str
         :rtype: int
         """
         if set(list(B)) > set(list(A)):
             return -1
         
         
         
         
         l_b = len(B)
         pointer_b = 0
         l_a = len(A)
         pointer_a = 0
 
         L = []
         while pointer_a < l_a:
             if A[pointer_a] == B[pointer_b]:
                 L.append(pointer_a)
             pointer_a += 1
 
         if L == []:
             return -1
 
         for pointer_a in L:
             times = 1
             while pointer_b < l_b:
                 if pointer_a == l_a:
                     pointer_a = 0
                     times += 1
                 if B[pointer_b] == A[pointer_a]:
                     pointer_b += 1
                     pointer_a += 1
                     continue
                 else:
                     break
             if pointer_b == l_b:
                 return times
             else:
                 pointer_b = 0
         return -1
 
 
 


class Solution:
     def repeatedStringMatch(self, A, B):
         k = int(len(B) / len(A))
         m = ""
         h = A + A[0]
         for i in range(len(B)-1):
             if B[i:i+2] not in h: return -1
         for i in range(k):
             m += A
         while B not in m:
             m += A
             k += 1
             if k>100: return -1
         return k


class Solution:
     def repeatedStringMatch(self, A, B):
         """
         :type A: str
         :type B: str
         :rtype: int
         """
         if A == B or B in A:
             return 1
         if A not in B:
             if B not in (A+A):
                 return -1
             else:
                 return 2
         else:
             count,i = 1, B.index(A)
             if i != 0:
                 if B[:i] != A[-i:]:
                     return -1
                 else:
                     count = 2
             while i+ 2*len(A) < len(B) and A == B[i+len(A):i+2*len(A)]:
                 count += 1
                 i = B.index(A, i+len(A))
             if i == len(B) - len(A):
                 return count
             else:
                 if B[i+len(A):] != A[:len(B)-i-len(A)]:
                     return -1
                 return count+1

class Solution:
     def repeatedStringMatch(self, A, B):
         """
         :type A: str
         :type B: str
         :rtype: int
         """
         for i in range(len(A)):
             if A[i] == B[0]:
                 divisible = True if (len(B)-(len(A)-i))%len(A) == 0 else False
                 time = 1 + (len(B)-(len(A)-i))//len(A) if divisible else 1 + (len(B)-(len(A)-i))//len(A) + 1
                 repeatA = A*time
                 if repeatA[i:i+len(B)] == B:
                     return time
         return -1

class Solution:
     def repeatedStringMatch(self, a, b):
         """
         :type A: str
         :type B: str
         :rtype: int
         """
         if a is None or len(a) ==0 or b is None or len(b) == 0:
             return -1
         if a == b:
             return 1
         kmp = [0 for _ in range(len(b)+1)]
         j = 0
         for i in range(1, len(b)):
             if b[j] == b[i]:
                 j += 1
                 kmp[i] = j
             else:
                 if j == 0:
                     i += 1
                 else:
                     j = kmp[j-1]
         j = 0
         for i in range(len(a)):
             while j < len(b) and a[(i+j)%len(a)] == b[j]:
                 j += 1
             if j == len(b):
                 return -(-(i+j)//len(a))
             j = kmp[j-1]
         return -1

class Solution:
     def repeatedStringMatch(self, text, pattern):
         n, m = len(text), len(pattern)
         
         base, prime = 256, 257
         
         bpow = base**(m-1) % prime
 
         def check(i):
             for j in range(m):
                 if text[(i + j) % n] != pattern[j]:
                     return False
             return True
         
         def compute_hash(s):
             n, h = len(s), 0
             for i in range(m):
                 c = s[i % n]
                 h = (h * base + ord(c)) % prime
             return h
 
         def update_hash(h, old, new):
             dh = (ord(old) * bpow) % prime
             h = (h - dh + prime) % prime
             h = (h * base + ord(new)) % prime
             return h
 
         p = compute_hash(pattern)
         t = compute_hash(text)
         
         for i in range(n):
             if t == p and check(i):
                 return 1 + (i + m - 1) // n
             t = update_hash(t, text[i], text[(i + m) % n])
         return -1