Given two strings A and B, find the minimum number of times A has to be repeated such that B becomes a substring of the repeated A. If B cannot be a substring of A no matter how many times it is repeated, return -1.
Example 1:
Input: A = "abcd", B = "cdabcdab"
Output: 3
Explanation: After repeating A three times, 
we get "abcdabcdabcd".
Example 2:
Input: A = "aa", B = "a"
Output: 1
Explanation: B is already a substring of A.
Your Task:  
You don't need to read input or print anything. Complete the function repeatedStringMatch() which takes strings A and B as input parameters and returns the minimum number of operations to complete the task. If it is not possible then return -1.
Expected Time Complexity: O(|A| * |B|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |A|, |B| ≤ 4 * 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def repeatedStringMatch(self, A, B):
        # code here

Solutions:
from math import ceil

class Solution:

	def repeatedStringMatch(self, a, b):
		if b in a:
			return 1
		n = len(a)
		m = len(b)
		count = ceil(m / n)
		if b in count * a:
			return count
		elif b in (count + 1) * a:
			return count + 1
		else:
			return -1


import math

class Solution:

	def repeatedStringMatch(self, A, B):
		n = math.ceil(len(B) / len(A))
		a = A * n
		for i in range(n + 1):
			if B in a:
				return n + i
			a = a + A
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		import math
		n = math.ceil(len(B) / len(A))
		if B in A * n:
			return n
		elif B in A * (n + 1):
			return n + 1
		return -1


class Solution:

	def repeatedStringMatch(self, a, b):
		i = 0
		ans = 1
		while i < len(a):
			f = 0
			if a[i] == b[0]:
				j = i
				k = 0
				while k < len(b):
					if a[j] != b[k]:
						f = 1
						break
					j += 1
					k += 1
					if j == len(a) and k != len(b):
						ans += 1
						j = 0
				if f == 0:
					break
			i += 1
		if f != 0 or i == len(a):
			return -1
		else:
			return ans


class Solution:

	def repeatedStringMatch(self, A, B):
		c = 0
		k = A
		if B in A:
			return 1
		for i in range(len(B) // len(A) + 2):
			if B in A:
				return c + 1
			else:
				A = A + k
				c = c + 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		a = set(A)
		b = set(B)
		ans = 0
		if b.issubset(A):
			S = ''
			while len(S) < len(B):
				S += A
				ans += 1
			if B in S:
				return ans
			elif B in S + A:
				return ans + 1
			else:
				return -1
		else:
			return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		repeat = len(B) // len(A)
		str = A
		count = 1
		for i in range(0, repeat + 2):
			if B in A:
				return count
			else:
				A = str + A
				count += 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		output = ''
		n = len(A)
		count = 1
		for i in range(n):
			if A[i:] == B[:n - i]:
				output += A[i:]
				break
		while len(output) < len(B):
			output += A
			count += 1
		return count if output[:len(B)] == B else -1


class Solution:

	def repeatedStringMatch(self, a, b):
		strA = a
		repeat = len(b) // len(a)
		count = 1
		for i in range(repeat + 2):
			if b in a:
				return count
			else:
				count += 1
				a += strA
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		if A == B:
			return 1
		c = len(B) // len(A)
		s = c * A
		t = (c + 1) * A
		w = (c + 2) * A
		if s.find(B) != -1:
			return c
		elif t.find(B) != -1:
			return c + 1
		elif w.find(B) != -1:
			return c + 2
		else:
			return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		q = (len(B) - 1) // len(A) + 1
		for i in range(2):
			if B in A * (q + i):
				return q + i
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		i = c = 0
		while True:
			a = A * i
			c = c + 1
			if a.find(B) != -1:
				return c - 1
			if len(a) > 2 * len(B):
				return -1
			else:
				i = i + 1


class Solution:

	def repeatedStringMatch(self, A, B):
		i = 1
		while 1 == 1:
			if B in A * i:
				return i
			if len(A * i) > 4 * len(B):
				return -1
			i += 1


class Solution:

	def repeatedStringMatch(self, A, B):
		len_a = len(A)
		len_b = len(B)
		for i in range(len_a):
			if A[i] == B[0]:
				k = i
				cnt = 1
				for j in range(len_b):
					if k >= len_a:
						k = 0
						cnt += 1
					if A[k] != B[j]:
						break
					k += 1
				else:
					return cnt
		return -1


class Solution:

	def repeatedStringMatch(self, a, b):
		if b in a:
			return 1
		s = a
		count = 1
		while len(s) < 4 * len(b):
			if b in s:
				return count
			else:
				s += a
				count += 1
		else:
			if b in s:
				return count
			else:
				return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		ans = 1
		cp = A
		while len(A) < len(B):
			ans += 1
			A += cp
		if B in A:
			return ans
		if B in A + cp:
			return ans + 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		a = A
		b = B
		l_b = len(b)
		x = ''
		count_of_repetitions = 0
		while len(x) <= len(b) * 2:
			if b in x:
				break
			x = x + a
			count_of_repetitions += 1
		if b in x:
			return count_of_repetitions
		else:
			return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		l_a = len(A)
		l_b = len(B)
		count = 1
		temp = A
		while len(A) < len(B):
			A += temp
			count += 1
		if B in A:
			return count
		if B in A + temp:
			return count + 1
		else:
			return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		lenA = len(A)
		lenB = len(B)
		repeated_str = ''
		cnt = 0
		while len(repeated_str) <= len(B):
			repeated_str = repeated_str + A
			cnt += 1
			if len(repeated_str) == len(B) and repeated_str == B:
				return cnt
		for i in range(2):
			if repeated_str.find(B) != -1:
				return i + cnt
			repeated_str = repeated_str + A
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		lenA = len(A)
		lenB = len(B)
		repeated_str = ''
		cnt = 0
		while len(repeated_str) <= 2 * len(B):
			repeated_str = repeated_str + A
			cnt += 1
			if repeated_str.find(B) != -1:
				return cnt
		res = repeated_str.find(B)
		return cnt if res >= 0 else -1


class Solution:

	def repeatedStringMatch(self, A, B):
		temp = ''
		count = 0
		while len(temp) < len(B):
			temp += A
			count += 1
			if B in temp:
				return count
		temp += A
		if B in temp:
			return count + 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		count = len(B) // len(A)
		if B in A:
			return 1
		elif B in count * A:
			return count
		elif B in A * (count + 1):
			return count + 1
		elif B in A * (count + 2):
			return count + 2
		else:
			return -1


class Solution:

	def repeatedStringMatch(self, a, b):
		a1 = a
		m = len(a)
		n = len(b)
		count = n - 1
		repeat = (n - 1) // m
		repeat += 1

		def subs(a, b):
			(s, j) = (0, 0)
			for i in range(len(a)):
				j = 0
				if a[i] == b[j]:
					s = i
					while s < len(a) and j < len(b):
						if a[s] == b[j]:
							s += 1
							j += 1
						else:
							j = 0
							break
					if j == len(b):
						return True
		i = 0
		count = 1
		while len(a) < len(b):
			a += a1
			count += 1
		if subs(a, b):
			return count
		else:
			a += a
			if subs(a, b):
				return count + 1
		return -1


class Solution:

	def repeatedStringMatch(self, a, b):
		a1 = a
		m = len(a)
		n = len(b)
		count = n - 1
		repeat = (n - 1) // m
		repeat += 1
		i = 0
		count = 1
		while len(a) < len(b):
			a += a1
			count += 1
		if b in a:
			return count
		else:
			a += a
			if b in a:
				return count + 1
		return -1


import math

class Solution:

	def repeatedStringMatch(self, A, B):
		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


class Solution:

	def repeatedStringMatch(self, A, B):
		n = len(A)
		m = len(B)
		check = m // n
		A1 = A * (check + 2)
		A2 = A * (check + 1)
		A3 = A * check
		if B in A3:
			return check
		if B in A2:
			return check + 1
		if B in A1:
			return check + 2
		else:
			return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		a_len = len(A)
		b_len = len(B)
		if b_len < a_len:
			if B in A:
				return 1
			elif B * 2 in A:
				return 2
		count1 = int(b_len / a_len)
		count2 = int(b_len / a_len) + 1
		count3 = int(b_len / a_len) + 2
		if B in A * count1:
			return count1
		elif B in A * count2:
			return count2
		elif B in A * count3:
			return count3
		else:
			return -1


class Solution:

	def issub(self, x, y):
		if x in y:
			return True
		return False

	def repeatedStringMatch(self, a, b):
		c = 1
		k = a
		while len(a) < len(b):
			a += k
			c += 1
		if self.issub(b, a):
			return c
		if self.issub(b, a + k):
			return c + 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		if B in A:
			return 1
		a1 = len(A)
		b1 = len(B)
		l = a1
		if len(A) >= l:
			if B in A:
				return 1
		temp = A * (len(B) // l)
		if B in temp:
			return len(B) // l
		temp = A * (len(B) // l + 1)
		if B in temp:
			return len(B) // l + 1
		temp = A * (len(B) // l + 2)
		if B in temp:
			return len(B) // l + 2
		return -1


class Solution:

	def repeatedStringMatch(self, a, b):
		counter = 1
		tmp = a
		while len(a) < len(b):
			a += tmp
			counter += 1
		if b in a:
			return counter
		if b in a + tmp:
			return counter + 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		x = ''
		count = 0
		while len(x) < len(A) + len(B):
			x += A
			count += 1
			if B in x:
				return count
		return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		A = input().strip()
		B = input().strip()
		obj = Solution()
		print(obj.repeatedStringMatch(A, B))


class Solution:

	def repeatedStringMatch(self, A, B):
		s = A
		ans = 1
		while len(A) < len(B):
			A += s
			ans += 1
		if B in A:
			return ans
		elif B in A + s:
			return ans + 1
		else:
			return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		A = input().strip()
		B = input().strip()
		obj = Solution()
		print(obj.repeatedStringMatch(A, B))


class Solution:

	def repeatedStringMatch(self, A, B):
		n = len(A)
		m = len(B)
		for i in range(n):
			if A[i] == B[0]:
				count = 1
				(j, k) = (0, i)
				while j < m:
					if k >= n:
						k = 0
						count += 1
					if A[k] != B[j]:
						break
					k += 1
					j += 1
				if j == m:
					return count
		return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		A = input().strip()
		B = input().strip()
		obj = Solution()
		print(obj.repeatedStringMatch(A, B))


class Solution:

	def repeatedStringMatch(self, A, B):
		n = len(A)
		old_n = n
		m = len(B)
		i = m // n
		A = A * (2 + i)
		n = n * (2 + i)
		for i in range(n - m + 1):
			if A[i:i + m] == B:
				size = i + m
				if size % old_n == 0:
					return size // old_n
				else:
					return size // old_n + 1
		return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		A = input().strip()
		B = input().strip()
		obj = Solution()
		print(obj.repeatedStringMatch(A, B))


class Solution:

	def repeatedStringMatch(self, A, B):
		if B in A:
			return 1
		count = len(B) // len(A)
		c = 1
		s = A
		for i in range(count + 2):
			if B in s:
				return c
			c += 1
			s = s + A
		return -1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		A = input().strip()
		B = input().strip()
		obj = Solution()
		print(obj.repeatedStringMatch(A, B))


from itertools import chain, cycle

class Solution:

	def repeatedStringMatch(self, A, B):
		if len(A) > len(B):
			if A.find(B) != -1:
				return 1
			if (A * 2).find(B) != -1:
				return 2
			else:
				return -1
		if A == B:
			return 1
		offset = 0
		double = A * 2
		for offset in range(len(A)):
			double = chain(A[offset:], A)
			for i in range(len(A)):
				if next(double) != B[i]:
					break
			else:
				break
		count = 1 if offset > 0 else 0
		repeated = cycle(A)
		for i in range(offset):
			next(repeated)
		for (x, y) in zip(B, repeated):
			if x != y:
				return -1
		reversed_offset = (len(A) - offset) % len(A)
		count += (len(B) - reversed_offset) // len(A)
		if (len(B) - reversed_offset) % len(A):
			count += 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		A = input().strip()
		B = input().strip()
		obj = Solution()
		print(obj.repeatedStringMatch(A, B))


class Solution:

	def repeatedStringMatch(self, A, B):
		c = 1
		d = 0
		for i in B:
			if i not in A:
				return -1
		D = A
		while c < 100:
			if B in A:
				return c
			A = A + D
			c += 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		count = 1
		tp = A
		while len(A) < len(B):
			A += tp
			count += 1
		if B in A:
			return count
		if B in A + tp:
			return count + 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		count = len(B) // len(A)
		x = A * count
		y = A * (count + 1)
		z = A * (count + 2)
		if B in x:
			return count
		elif B in y:
			return count + 1
		elif B in z:
			return count + 2
		else:
			return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		temp = A
		_count = 1
		for i in range(100):
			if B not in temp:
				temp += A
				_count += 1
			else:
				return _count
		return -1


from math import ceil

class Solution:

	def repeatedStringMatch(self, A, B):
		if len(B) < len(A):
			p = 2 * A
			if B in A:
				return 1
			if B in p:
				return 2
			return -1
		if len(B) >= len(A):
			count = ceil(len(B) / len(A))
			r = count * A
			s = (count + 1) * A
			if B in r:
				return count
			if B in s:
				return count + 1
			return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		temp = A
		for i in range(1, 100):
			if B in temp:
				return i
			temp += A
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		if len(A) >= len(B):
			if B in A:
				return 1
			for i in range(1, len(B)):
				if A.startswith(B[i:]) and A.endswith(B[:i]):
					return 2
			return -1
		mult = len(B) // len(A) + (1 if len(B) % len(A) else 0)
		new_A = mult * A
		match = self.repeatedStringMatch(new_A, B)
		if match == 1:
			return mult
		elif match == 2:
			return mult + 1
		else:
			return -1


class Solution:

	def repeatedStringMatch(self, A, B):

		def check(p, q):
			n = len(p)
			m = len(q)
			for i in range(n - m + 1):
				if p[i:i + m] == q:
					return True
			return False
		st = A
		count = 1
		while len(A) < len(B):
			A = A + st
			count += 1
		if check(A, B):
			return count
		if check(A + st, B):
			return count + 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		count = 0
		s = ''
		while len(B) + len(A) >= len(s):
			if s.find(B) == -1:
				count += 1
				s += A
			else:
				break
		if s.find(B) == -1:
			return -1
		else:
			return count


class Solution:

	def repeatedStringMatch(self, a, b):
		m = len(a)
		n = len(b)
		temp = a
		count = 1
		if n == 0:
			return 0
		while m < n:
			a += temp
			count = count + 1
			m = len(a)
		store = search(b, a)
		if store == 1:
			return count
		elif store == 0:
			count += 1
			a += temp
			store2 = search(b, a)
			if store2 == 1:
				return count
			else:
				return -1

def search(pat, txt):
	M = len(pat)
	N = len(txt)
	i = 0
	j = 0
	p = 0
	t = 0
	h = 1
	q = 1000000007
	flag = 0
	d = 256
	for i in range(M - 1):
		h = h * d % q
	for i in range(M):
		p = (d * p + ord(pat[i])) % q
		t = (d * t + ord(txt[i])) % q
	for i in range(N - M + 1):
		if p == t:
			for j in range(M):
				if txt[i + j] != pat[j]:
					break
				else:
					j += 1
			if j == M:
				flag = 1
				return flag
		if i < N - M:
			t = (d * (t - ord(txt[i]) * h) + ord(txt[i + M])) % q
			if t < 0:
				t = t + q
	return flag


class Solution:

	def repeatedStringMatch(self, A, B):
		(n, m) = (len(A), len(B))
		if m <= n:
			if B in A:
				return 1
			elif B in A * 2:
				return 2
			else:
				return -1
		k = 1
		t = A
		while len(A) < len(B):
			k += 1
			A += t
		if B in A:
			return k
		k += 1
		A += t
		if B in A:
			return k
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		if B in A:
			return 1
		s = ''
		count = 0
		l = len(A) + len(B)
		while l >= len(s):
			s += A
			count += 1
			if B in s:
				return count
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		iter_length = len(B) // len(A)
		ans = 1
		S = A
		for i in range(iter_length + 2):
			if B in S:
				return ans
			S = S + A
			ans += 1
		return -1


class Solution:

	def repeatedStringMatch(self, a, b):
		import math
		n1 = len(a)
		n2 = len(b)
		n = math.ceil(n2 / n1)
		t = a * n
		for i in range(n1 * n - n2 + 1):
			if t[i:i + n2] == b:
				return n
		n += 1
		t = a * n
		for i in range(n1 * n - n2 + 1):
			if t[i:i + n2] == b:
				return n
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		la = len(A)
		lb = len(B)
		for i in range(la):
			count = 1
			k = i
			for j in range(lb):
				if k == la:
					k = 0
					count += 1
				if A[k] != B[j]:
					break
				k += 1
			else:
				return count
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		if B in A:
			return 1
		if len(set(B) - set(A)) > 0:
			return -1
		return self.solve(A, B, 0)

	def solve(self, A, B, i):
		if i >= len(B):
			return 0
		if A.startswith(B[i:]):
			return 1
		lA = len(A)
		if i == 0:
			res = None
			for j in range(lA):
				if B.startswith(A[j:]):
					tmp = self.solve(A, B, i + lA - j)
					if tmp >= 0:
						if res is None or res > tmp:
							res = tmp
			if res is None:
				res = -1
		elif A == B[i:i + lA]:
			res = self.solve(A, B, i + lA)
		else:
			return -1
		if res >= 0:
			return res + 1
		return res


class Solution:

	def repeatedStringMatch(self, A, B):
		count = len(B) // len(A)
		for i in range(5):
			if B in A * (count + i):
				return count + i
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		x = A
		if A.count(B) > 0:
			return 1
		else:
			c = 1
			while len(A) < len(B):
				A += x
				c += 1
			if A.count(B) > 0:
				return c
			A += x
			c += 1
			if A.count(B) > 0:
				return c
			return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		t = 0
		for i in B:
			if i not in A:
				return -1
		if B in A:
			return 1
		c = len(B) // len(A)
		j = 0
		while t == 0 and j < 4:
			if B in A * c:
				t = 1
				return c
			c = c + 1
			j = j + 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		a = len(A)
		b = len(B)
		x = b // a
		a1 = A * x
		a2 = A * (x + 1)
		a5 = A * (x + 2)
		a3 = a1.find(B)
		a4 = a2.find(B)
		a6 = a5.find(B)
		if a3 != -1:
			return x
		elif a4 != -1:
			return x + 1
		elif a6 != -1:
			return x + 2
		else:
			return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		x = ''
		for i in B:
			if i not in A:
				return -1
		for i in range(100):
			x += A
			if B in x:
				return i + 1
				break
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		count = int(len(B) // len(A))
		A1 = A * count
		A2 = A * (count + 1)
		A3 = A * (count + 2)
		if B in A:
			return 1
		elif B in A1:
			return count
		elif B in A2:
			return count + 1
		elif B in A3:
			return count + 2
		else:
			return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		n = len(A)
		m = len(B)
		if n > m:
			if B in A:
				return 1
		r = 9500 // n
		s = 1
		while s < r:
			if B in A * s:
				return s
			s += 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		alen = len(A)
		blen = len(B)
		if blen < alen:
			if B in A:
				return 1
			elif B in A * 2:
				return 2
		count1 = int(blen / alen)
		count2 = int(blen / alen) + 1
		count3 = int(blen / alen) + 2
		if B in A * count1:
			return count1
		if B in A * count2:
			return count2
		if B in A * count3:
			return count3
		else:
			return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		t = ''
		count = 0
		k = len(A) + len(B)
		while k >= len(t):
			t += A
			count += 1
			if t.find(B) != -1:
				return count
		if t.find(B) != -1:
			return count
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		count = 1
		s = A
		while count < 100:
			if B in A:
				return count
			else:
				A = A + s
				count = count + 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		s = A
		ret = 1
		while len(s) < len(B):
			s += A
			ret += 1
		if B in s:
			return ret
		if B in s + A:
			return ret + 1
		return -1


class Solution:

	def verify(self, start, A, B):
		index = 1
		a_reps = 1
		while index < len(B):
			a_index = (start + index) % len(A)
			if B[index] != A[a_index]:
				return 0
			if a_index == 0:
				a_reps += 1
			index += 1
		return a_reps

	def repeatedStringMatch(self, A, B):
		for (i, ch) in enumerate(A):
			if ch == B[0]:
				reps = self.verify(i, A, B)
				if reps:
					return reps
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		_len = len(A) + len(B)
		cnt = 0
		S = ''
		if A == B:
			return 1
		while len(S) < _len:
			S += A
			cnt += 1
			if B in S:
				break
		if B in S:
			return cnt
		else:
			return -1


class Solution:

	def repeatedStringMatch(self, a, b):
		s = a
		c = 1
		while len(s) < len(b):
			s += a
			c += 1
		if s.find(b) != -1:
			return c
		s += a
		if s.find(b) != -1:
			return c + 1
		return -1


class Solution:

	def is_substring(self, haystack, needle):
		(m, n) = (len(haystack), len(needle))
		new_string = needle + '#' + haystack
		len_str = len(new_string)
		lps = [0 for _ in range(len_str)]
		start = 0
		for end in range(1, len_str):
			while start > 0 and new_string[start] != new_string[end]:
				start = lps[start - 1]
			if new_string[start] == new_string[end]:
				start += 1
			lps[end] = start
			if start == n:
				return True

	def repeatedStringMatch(self, A, B):
		new_string = ''
		count = 0
		while len(new_string) < len(B):
			new_string += A
			count += 1
		if self.is_substring(new_string, B):
			return count
		new_string += A
		if self.is_substring(new_string, B):
			return count + 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		(n, m) = (len(A), len(B))
		mini = 0
		for i in range(n):
			k = i
			mini = int(k > 0)
			for j in range(len(B)):
				if k == 0:
					mini += 1
				if A[k] != B[j]:
					break
				if j == m - 1 and A[k] == B[j]:
					return mini
				k = (k + 1) % n
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		d = len(B) // len(A) + 1
		st = A
		for i in range(d + 1):
			if B in st:
				return i + 1
			st += A
		return -1


class Solution:

	def repeatedStringMatch(self, a, b):
		count = 1
		temp = a
		while len(a) < len(b):
			count += 1
			a += temp
		if a.find(b) != -1:
			return count
		a += temp
		if a.find(b) != -1:
			return count + 1
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		s = A
		x = 1
		m = len(B) // len(A) + 2
		while True:
			if B in A:
				return x
			else:
				A = A + s
			x = x + 1
			if x > m:
				break
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		string = ''
		for i in range(1, 100):
			if B in string:
				return i - 1
			else:
				string += A
		return -1


class Solution:

	def repeatedStringMatch(self, A, B):
		m = len(A)
		n = len(B)
		tp = A
		ans = 1
		while len(A) < len(B):
			A += tp
			ans += 1
		if self.check(A, B):
			return ans
		if self.check(A + tp, B):
			return ans + 1
		return -1

	def check(self, s1, s2):
		if s2 in s1:
			return True
		return False