Given two strings A and B. The task is to find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution exists, print -1.
Examples:
Input : A = “abcd”, B = “cdabcdab”
Output : 3
Repeating A three times (“abcdabcdabcd”), B is a substring of it. B is not a substring of A when it is repeated less than 3 times.
Input : A = “ab”, B = “cab”
Output : -1
Approach :
Imagine we wrote S = A+A+A+… If B is a substring of S, we only need to check whether some index 0 or 1 or …. length(A) -1 starts with B, as S is long enough to contain B, and S has a period of length(A).
Now, suppose ans is the least number for which length(B) <= length(A * ans). We only need to check whether B is a substring of A * ans or A * (ans+1). If we try k < ans, then B has a larger length than A * ans and therefore can’t be a substring. When k = ans+1, A * k is already big enough to try all positions for B( A[i:i+length(B)] == B for i = 0, 1, …, length(A) – 1).
Below is the implementation of the above approach:
C
#include <stdio.h>
#include <string.h>
int issubstring(char* str2, char* rep1)
{
int M = strlen(str2);
int N = strlen(rep1);
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++)
if (rep1[i + j] != str2[j])
break;
if (j == M)
return 1;
}
return 0;
}
int Min_repetation(char* A, char* B)
{
int ans = 1;
char *S = A;
while(strlen(S) < strlen(B))
{
strcat(S, A);
ans++;
}
if (issubstring(B, S)) return ans;
char *temp=S;
strcat(temp,A);
if (issubstring(B,temp))
return ans + 1;
return -1;
}
int main()
{
char A[] = "abcd", B[] = "cdabcdab";
printf("%d", Min_repetation(A, B));
return 0;
}
|
C++
#include <bits/stdc++.h>
using namespace std;
bool issubstring(string str2, string rep1)
{
int M = str2.length();
int N = rep1.length();
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++)
if (rep1[i + j] != str2[j])
break;
if (j == M)
return true;
}
return false;
}
int Min_repetation(string A, string B)
{
int ans = 1;
string S = A;
while(S.size() < B.size())
{
S += A;
ans++;
}
if (issubstring(B, S)) return ans;
if (issubstring(B, S+A))
return ans + 1;
return -1;
}
int main()
{
string A = "abcd", B = "cdabcdab";
cout << Min_repetation(A, B);
return 0;
}
|
Java
class GFG
{
static boolean issubstring(String str2,
String rep1)
{
int M = str2.length();
int N = rep1.length();
for (int i = 0; i <= N - M; i++)
{
int j;
for (j = 0; j < M; j++)
if (rep1.charAt(i + j) != str2.charAt(j))
break;
if (j == M)
return true;
}
return false;
}
static int Min_repetation(String A, String B)
{
int ans = 1;
String S = A;
while(S.length() < B.length())
{
S += A;
ans++;
}
if (issubstring(B, S)) return ans;
if (issubstring(B, S + A))
return ans + 1;
return -1;
}
public static void main(String[] args)
{
String A = "abcd", B = "cdabcdab";
System.out.println(Min_repetation(A, B));
}
}
|
Python3
def min_repetitions(a, b):
len_a = len(a)
len_b = len(b)
for i in range(0, len_a):
if a[i] == b[0]:
k = i
count = 1
for j in range(0, len_b):
if k >= len_a:
k = 0
count = count + 1
if a[k] != b[j]:
break
k = k + 1
else:
return count
return -1
A = 'abcd'
B = 'cdabcdab'
print(min_repetitions(A, B))
|
C#
using System;
class GFG
{
static Boolean issubstring(String str2,
String rep1)
{
int M = str2.Length;
int N = rep1.Length;
for (int i = 0; i <= N - M; i++)
{
int j;
for (j = 0; j < M; j++)
if (rep1[i + j] != str2[j])
break;
if (j == M)
return true;
}
return false;
}
static int Min_repetation(String A, String B)
{
int ans = 1;
String S = A;
while(S.Length < B.Length)
{
S += A;
ans++;
}
if (issubstring(B, S)) return ans;
if (issubstring(B, S + A))
return ans + 1;
return -1;
}
public static void Main(String[] args)
{
String A = "abcd", B = "cdabcdab";
Console.WriteLine(Min_repetation(A, B));
}
}
|
Javascript
<script>
function issubstring(str2, rep1)
{
var M = str2.length;
var N = rep1.length;
for (var i = 0; i <= N - M; i++) {
var j;
for (j = 0; j < M; j++)
if (rep1[i + j] != str2[j])
break;
if (j == M)
return true;
}
return false;
}
function Min_repetation(A, B)
{
var ans = 1;
var S = A;
while(S.length < B.length)
{
S += A;
ans++;
}
if (issubstring(B, S))
return ans;
if (issubstring(B, S+A))
return ans + 1;
return -1;
}
var A = "abcd", B = "cdabcdab";
document.write( Min_repetation(A, B));
</script>
|
Time Complexity: O(N * M)
Auxiliary Space: O(1).
Approach 2:
Idea here is to try and find the string using a brute force string searching algorithm (n * m). The only difference here is to calculate the modulus (i % n) when the counter reaches the end of the string.
Below is the implementation of the above approach:
C
#include <stdio.h>
#include <string.h>
int repeatedStringMatch(char* A, char* B)
{
int m = strlen(A);
int n = strlen(B);
int count;
int found = 0;
for (int i = 0; i < m; i++) {
int j = i;
int k = 0;
count = 1;
while (k < n && A[j] == B[k]) {
if (k == n - 1) {
found = 1;
break;
}
j = (j + 1) % m;
if (j == 0)
count++;
k++;
}
if (found)
return count;
}
return -1;
}
int main()
{
char A[] = "abcd";
char B[] = "cdabcdab";
printf("%d",repeatedStringMatch(A, B));
return 0;
}
|
C++
#include <bits/stdc++.h>
using namespace std;
int repeatedStringMatch(string A, string B)
{
int m = A.length();
int n = B.length();
int count;
bool found = false;
for (int i = 0; i < m; i++) {
int j = i;
int k = 0;
count = 1;
while (k < n && A[j] == B[k]) {
if (k == n - 1) {
found = true;
break;
}
j = (j + 1) % m;
if (j == 0)
count++;
k++;
}
if (found)
return count;
}
return -1;
}
int main()
{
string A = "abcd";
string B = "cdabcdab";
cout << repeatedStringMatch(A, B);
return 0;
}
|
Java
import java.io.*;
class GFG {
static int repeatedStringMatch(String A, String B)
{
int m = A.length();
int n = B.length();
int count;
boolean found = false;
for (int i = 0; i < m; ++i) {
int j = i;
int k = 0;
count = 1;
while (k < n && A.charAt(j) == B.charAt(k)) {
if (k == n - 1) {
found = true;
break;
}
j = (j + 1) % m;
if (j == 0)
++count;
k += 1;
}
if (found)
return count;
}
return -1;
}
public static void main(String[] args)
{
String A = "abcd", B = "cdabcdab";
System.out.println(repeatedStringMatch(A, B));
}
}
|
Python
def repeatedStringMatch(A, B):
m = len(A)
n = len(B)
count = 0
found = False
for i in range(m):
j = i
k = 0
count = 1
while k < n and A[j] == B[k] :
if (k == n - 1) :
found = True
break
j = (j + 1) % m
if (j == 0):
count = count + 1
k = k + 1
if (found):
return count
return -1
A = "abcd";
B = "cdabcdab";
print(repeatedStringMatch(A, B));
|
C#
using System;
class GFG
{
static int repeatedStringMatch(string A, string B)
{
int m = A.Length;
int n = B.Length;
int count;
bool found = false;
for (int i = 0; i < m; i++) {
int j = i;
int k = 0;
count = 1;
while (k < n && A[j] == B[k]) {
if (k == n - 1) {
found = true;
break;
}
j = (j + 1) % m;
if (j == 0)
count++;
k++;
}
if (found)
return count;
}
return -1;
}
public static void Main(String[] args)
{
String A = "abcd", B = "cdabcdab";
Console.WriteLine(repeatedStringMatch(A, B));
}
}
|
Javascript
<script>
function repeatedStringMatch(A, B)
{
let m = A.length;
let n = B.length;
let count;
let found = false;
for (let i = 0; i < m; i++) {
let j = i;
let k = 0;
count = 1;
while (k < n && A[j] == B[k]) {
if (k == n - 1) {
found = true;
break;
}
j = (j + 1) % m;
if (j == 0)
count++;
k++;
}
if (found)
return count;
}
return -1;
}
let A = "abcd";
let B = "cdabcdab";
document.write(repeatedStringMatch(A, B));
</script>
|
Time Complexity: O(N * M)
Auxiliary Space: O(1).
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!