Problem Statement:
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".
Examples:
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.
Time Complexity:
repeatedStringMatch = O(m)
rabinKarp (avg) = O(n + m)
rabinKarp (worst) = O(n * m)
Space Complexity:
repeatedStringMatch = O(m)
rabinKarp (avg) = O(1)
rabinKarp (worst) = O(1)
Approach (Repeated String Match):
Start with text = a and count = 1.
Keep appending a to text until its length becomes at least equal to b.
Check if b is a substring of text:
If yes → return count.
Append a one more time (to handle overlap cases).
Check again:
If found → return updated count.
If still not found → return -1.
Approach (Rabin-Karp for substring check):
Compute hash of pattern (b) and first window of text.
Slide the cpde window over text.
If hash matches → verify using substring comparison.
Update hash using rolling hash technique:</p>
Remove left character.
Add next character.
If match found → return true, else false.
Dry Run
Input: a = "abcd", b = "cdabcdab"
========================
PART 1: Build String
========================
Initial:
count = 1
text = "abcd"
While loop (text.length < b.length):
Iteration 1:
text.length = 4 < 8
text = "abcdabcd"
count = 2
Now:
text.length = 8 → exit loop
Check using Rabin-Karp instead of includes()
========================
PART 2: Rabin-Karp Matching
========================
text = "abcdabcd"
pattern = "cdabcdab"
n = 8, m = 8
Step 1: Compute initial hashes
patternHash = hash("cdabcdab")
windowHash = hash("abcdabcd")
→ patternHash ≠ windowHash → no match
No more window possible (n - m = 0)
Return false
========================
PART 3: Add One More Repeat
========================
text = "abcdabcdabcd"
count = 3
Now check again using Rabin-Karp
n = 12, m = 8
Step 1: Initial window "abcdabcd"
windowHash ≠ patternHash → no match
------------------------
Slide window
------------------------
i = 1 → window = "bcdabcda"
windowHash ≠ patternHash
i = 2 → window = "cdabcdab"
windowHash == patternHash
Double check substring:
text.substring(2, 10) = "cdabcdab" ✔ matches
Return true
========================
FINAL
========================
count = 3 → return 3
Output: 3
var repeatedStringMatch = function(a, b) {
let count = 1;
let text = a;
// Keep appending until length >= b
while (text.length < b.length) {
text += a;
count++;
}
// Check if b is now a substring
if (text.includes(b)) return count;
// One extra append (edge case)
text += a;
count++;
if (text.includes(b)) return count;
return -1;
};
// Rabin-Karp Algorithm
function rabinKarp(text, pattern) {
let base = 256;
let mod = 1e9 + 7;
let n = text.length;
let m = pattern.length;
let patternHash = 0;
let windowHash = 0;
// Initial hash
for (let i = 0; i < m; i++) {
patternHash = (patternHash * base + pattern.charCodeAt(i)) % mod;
windowHash = (windowHash * base + text.charCodeAt(i)) % mod;
}
let power = 1;
for (let i = 0; i < m - 1; i++) {
power = (power * base) % mod;
}
for (let i = 0; i <= n - m; i++) {
// Check hash match
if (patternHash === windowHash) {
if (text.substring(i, i + m) === pattern) {
return true;
}
}
// Rolling hash update
if (i < n - m) {
windowHash = (windowHash - (power * text.charCodeAt(i)) % mod + mod) % mod;
windowHash = (windowHash * base + text.charCodeAt(i + m)) % mod;
}
}
return false;
}
def repeatedStringMatch(a, b):
count = 1
text = a
while len(text) < len(b):
text += a
count += 1
if b in text:
return count
text += a
count += 1
if b in text:
return count
return -1
def rabinKarp(text, pattern):
base = 256
mod = int(1e9 + 7)
n = len(text)
m = len(pattern)
patternHash = 0
windowHash = 0
for i in range(m):
patternHash = (patternHash * base + ord(pattern[i])) % mod
windowHash = (windowHash * base + ord(text[i])) % mod
power = 1
for _ in range(m - 1):
power = (power * base) % mod
for i in range(n - m + 1):
if patternHash == windowHash:
if text[i:i+m] == pattern:
return True
if i < n - m:
windowHash = (windowHash - (power * ord(text[i])) % mod + mod) % mod
windowHash = (windowHash * base + ord(text[i + m])) % mod
return False
class Solution {
public int repeatedStringMatch(String a, String b) {
int count = 1;
StringBuilder text = new StringBuilder(a);
while (text.length() < b.length()) {
text.append(a);
count++;
}
if (text.toString().contains(b)) return count;
text.append(a);
count++;
if (text.toString().contains(b)) return count;
return -1;
}
public boolean rabinKarp(String text, String pattern) {
int base = 256;
int mod = (int)1e9 + 7;
int n = text.length();
int m = pattern.length();
long patternHash = 0, windowHash = 0;
for (int i = 0; i < m; i++) {
patternHash = (patternHash * base + pattern.charAt(i)) % mod;
windowHash = (windowHash * base + text.charAt(i)) % mod;
}
long power = 1;
for (int i = 0; i < m - 1; i++) {
power = (power * base) % mod;
}
for (int i = 0; i <= n - m; i++) {
if (patternHash == windowHash) {
if (text.substring(i, i + m).equals(pattern)) {
return true;
}
}
if (i < n - m) {
windowHash = (windowHash - (power * text.charAt(i)) % mod + mod) % mod;
windowHash = (windowHash * base + text.charAt(i + m)) % mod;
}
}
return false;
}
}
#include
using namespace std;
int repeatedStringMatch(string a, string b) {
int count = 1;
string text = a;
while (text.length() < b.length()) {
text += a;
count++;
}
if (text.find(b) != string::npos) return count;
text += a;
count++;
if (text.find(b) != string::npos) return count;
return -1;
}
bool rabinKarp(string text, string pattern) {
int base = 256;
long long mod = 1e9 + 7;
int n = text.length(), m = pattern.length();
long long patternHash = 0, windowHash = 0;
for (int i = 0; i < m; i++) {
patternHash = (patternHash * base + pattern[i]) % mod;
windowHash = (windowHash * base + text[i]) % mod;
}
long long power = 1;
for (int i = 0; i < m - 1; i++) {
power = (power * base) % mod;
}
for (int i = 0; i <= n - m; i++) {
if (patternHash == windowHash) {
if (text.substr(i, m) == pattern) return true;
}
if (i < n - m) {
windowHash = (windowHash - (power * text[i]) % mod + mod) % mod;
windowHash = (windowHash * base + text[i + m]) % mod;
}
}
return false;
}
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define BASE 256
#define MOD 1000000007
int repeatedStringMatch(char *a, char *b) {
static char text[10000];
strcpy(text, a);
int count = 1;
while (strlen(text) < strlen(b)) {
strcat(text, a);
count++;
}
if (strstr(text, b)) return count;
strcat(text, a);
count++;
if (strstr(text, b)) return count;
return -1;
}
bool rabinKarp(char *text, char *pattern) {
int n = strlen(text), m = strlen(pattern);
long long patternHash = 0, windowHash = 0;
for (int i = 0; i < m; i++) {
patternHash = (patternHash * BASE + pattern[i]) % MOD;
windowHash = (windowHash * BASE + text[i]) % MOD;
}
long long power = 1;
for (int i = 0; i < m - 1; i++) {
power = (power * BASE) % MOD;
}
for (int i = 0; i <= n - m; i++) {
if (patternHash == windowHash) {
if (strncmp(text + i, pattern, m) == 0) return true;
}
if (i < n - m) {
windowHash = (windowHash - (power * text[i]) % MOD + MOD) % MOD;
windowHash = (windowHash * BASE + text[i + m]) % MOD;
}
}
return false;
}
using System;
class Solution
{
public int RepeatedStringMatch(string a, string b)
{
int count = 1;
string text = a;
while (text.Length < b.Length)
{
text += a;
count++;
}
if (text.Contains(b)) return count;
text += a;
count++;
if (text.Contains(b)) return count;
return -1;
}
public bool RabinKarp(string text, string pattern)
{
int baseVal = 256;
int mod = (int)1e9 + 7;
int n = text.Length, m = pattern.Length;
long patternHash = 0, windowHash = 0;
for (int i = 0; i < m; i++)
{
patternHash = (patternHash * baseVal + pattern[i]) % mod;
windowHash = (windowHash * baseVal + text[i]) % mod;
}
long power = 1;
for (int i = 0; i < m - 1; i++)
{
power = (power * baseVal) % mod;
}
for (int i = 0; i <= n - m; i++)
{
if (patternHash == windowHash)
{
if (text.Substring(i, m) == pattern) return true;
}
if (i < n - m)
{
windowHash = (windowHash - (power * text[i]) % mod + mod) % mod;
windowHash = (windowHash * baseVal + text[i + m]) % mod;
}
}
return false;
}
}
