#686

Repeated String Match

expert · 1060 · lc medium +32 · verified · 38.4% accepted · 2,867 likes · top 17%

⚑ KMP Pattern Matching ⚑ Rolling Hash / Rabin-Karp

Description

Given two strings a and b, find the fewest number of times a must be repeated end-to-end so that b appears as a substring of the result. If no amount of repetition makes this possible, return -1.

Note: repeating "abc" zero times gives "", once gives "abc", twice gives "abcabc", and so on.

Example 1:

Input: a = "abcd", b = "cdabcdab"

Output: 3

Explanation: We return 3 because by repeating a three times "abcdabcdabcd", b is a substring of it.

Example 2:

Input: a = "a", b = "aa"

Output: 2

Code

1

2

3

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

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