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.

Source: leetcode | Difficulty: EASY
Tags: String algorithms

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

Solutions:
class Solution:

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

		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):

	def repeatedStringMatch1(self, A, B):

		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

	def repeatedStringMatch(self, A, B):

		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
		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):
		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):
		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):
		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):
		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
			elif 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