# 686. Repeated String Match

## Problem

Given two strings, A and B. How many times we need to repeat A, so that B is a substring of A.

## Solution

Repeat A until the string is as long as 2*len(B) - 1, which is the maximum length needed to find the answer. Use Rabin-Karp to hash the first len(B) chars in A, and sliding window one char by one char to the right. Compare each of the hash value of the substrings to the hash value of B. If not equal, then the substring is not B. If equal, we check char by char to see if the substring is B or not.

## Code

# Simple solution
class Solution:
def repeatedStringMatch(self, A: str, B: str) -> int:
x = (len(B) - 1) // len(A) + 1
if B in A * x:
return x
if B in A * (x + 1):
return x + 1
return -1


# Karp-Rabin
MOD = int((10 ** 9) + 7)
BASE = 26

class Solution:
def validate(self, index, A, B):
for i in range(len(B)):
if index - i < 0:
break
if A[(index - i) % len(A)] != B[-1 - i]:
return False
return True

def repeatedStringMatch(self, A: str, B: str) -> int:
b_value = 0
for char in B:
b_value = (b_value * BASE) % MOD + ord(char) - ord('a')
b_value %= MOD
hash_value = 0
multiplier = 1

for i in range(len(B)):
multiplier = (multiplier * BASE) % MOD

index = 0

while index < max(len(B) * 2, len(A) * 2):
hash_value = (ord(A[index % len(A)]) - ord('a') + (hash_value * BASE) % MOD) % MOD
if index >= len(B):
hash_value -= ((ord(A[(index - len(B)) % len(A)]) - ord('a')) * multiplier) % MOD
hash_value = (hash_value + MOD) % MOD
if hash_value == b_value and index >= len(B) - 1:
if self.validate(index, A, B):
return index // len(A) + 1
index += 1

return -1

# KMP
class Solution:

def repeatedStringMatch(self, A: str, B: str) -> int:
link = [-1] * (len(B) + 1)

for j in range(len(B) - 1):
i = j
while i != -1 and B[j + 1] != B[link[i] + 1]: