## Algorithm

Problem Name: 686. Repeated String Match

Given two strings `a` and `b`, return the minimum number of times you should repeat string `a` so that string `b` is a substring of it. If it is impossible for `b`​​​​​​ to be a substring of `a` after repeating it, return `-1`.

Notice: string `"abc"` repeated 0 times is `""`, repeated 1 time is `"abc"` and repeated 2 times is `"abcabc"`.

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
```

Constraints:

• `1 <= a.length, b.length <= 104`
• `a` and `b` consist of lowercase English letters.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int repeatedStringMatch(string A, string B) {
int i = 0, j = 0, count = 1;
while(j  <  B.size()){
while(i < A.size() && A[i] != B[j]) i++;
if(i == A.size() || count > 1) return -1;
while(j < B.size() && A[i++] == B[j++]){
if(j == B.size()) return count;
if(i == A.size()> i = 0, count++;
}
j = 0;
}
}
};
``````
Copy The Code &

Input

cmd
a = "abcd", b = "cdabcdab"

Output

cmd
3

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const repeatedStringMatch = function(A, B) {
let count = Math.ceil(B.length / A.length);
let testString = A.repeat(count)

return testString.includes(B) ? count : (testString + A).includes(B) ? count + 1 : -1
};
``````
Copy The Code &

Input

cmd
a = "abcd", b = "cdabcdab"

Output

cmd
3

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def repeatedStringMatch(self, A: str, B: str) -> int:
for i in range(1,2+len(B)//len(A)+1):
if B in A*i: return i
return -1
``````
Copy The Code &

Input

cmd
a = "a", b = "aa"

Output

cmd
2

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Numerics;

namespace LeetCode
{
public class _0686_RepeatedStringMatch
{
public int RepeatedStringMatch(string A, string B)
{
int q = (B.Length - 1) / A.Length + 1;
int p = 113, MOD = 1_000_000_007;
int pInv = (int)BigInteger.ModPow(p, MOD - 2, MOD);

long bHash = 0, power = 1;
for (int i = 0; i  <  B.Length; i++)
{
bHash += power * B[i];
bHash %= MOD;
power = (power * p) % MOD;
}

long aHash = 0; power = 1;
for (int i = 0; i  <  B.Length; i++)
{
aHash += power * A[i % A.Length];
aHash %= MOD;
power = (power * p) % MOD;
}

if (aHash == bHash && Check(0, A, B)) return q;
power = (power * pInv) % MOD;

for (int i = B.Length; i  <  (q + 1) * A.Length; i++)
{
aHash -= A[(i - B.Length) % A.Length];
aHash *= pInv;
aHash += power * A[i % A.Length];
aHash %= MOD;

if (aHash == bHash && Check(i - B.Length + 1, A, B))
return i  <  q * A.Length ? q : q + 1;
}
return -1;
}

private bool Check(int index, string A, string B)
{
for (int i = 0; i  <  B.Length; i++)
{
if (A[(i + index) % A.Length] != B[i])
{
return false;
}
}
return true;
}
}
}
``````
Copy The Code &

Input

cmd
a = "a", b = "aa"

Output

cmd
2