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.

Algorithms

Rabin-Karp

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]:
                i = link[i]
            link[j + 1] = link[i] + 1
        b_index = -1
        for i in range(-1, len(A) + len(B)):
            if b_index == len(B) - 1:
                return i // len(A) + 1
            while A[(i + 1) % len(A)] != B[b_index + 1] and b_index != -1:
                b_index = link[b_index]
            if A[(i + 1) % len(A)] == B[b_index + 1]:
                b_index += 1
                continue
        return -1