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 <= 104aandbconsist 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;
}
}
};
Input
Output
#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
};
Input
Output
#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
Input
Output
#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;
}
}
}
Input
Output