Minimum number of times A has to be repeated such that B is a substring of it
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
// C program to find Minimum number of times A // has to be repeated such that B is a substring of it #include <stdio.h> #include <string.h> // Function to check if a number // is a substring of other or not int issubstring( char * str2, char * rep1) { int M = strlen (str2); int N = strlen (rep1); // Check for substring from starting // from i'th index of main string for ( int i = 0; i <= N - M; i++) { int j; // For current index i, // check for pattern match for (j = 0; j < M; j++) if (rep1[i + j] != str2[j]) break ; if (j == M) // pattern matched return 1; } return 0; // not a substring } // Function to find Minimum number of times A // has to be repeated such that B is a substring of it int Min_repetation( char * A, char * B) { // To store minimum number of repetitions int ans = 1; // To store repeated string char *S = A; // Until size of S is less than B while ( strlen (S) < strlen (B)) { strcat (S, A); ans++; } // ans times repetition makes required answer if (issubstring(B, S)) return ans; char *temp=S; strcat (temp,A); // Add one more string of A if (issubstring(B,temp)) return ans + 1; // If no such solution exists return -1; } // Driver code int main() { char A[] = "abcd" , B[] = "cdabcdab" ; // Function call printf ( "%d" , Min_repetation(A, B)); return 0; } |
C++
// CPP program to find Minimum number of times A // has to be repeated such that B is a substring of it #include <bits/stdc++.h> using namespace std; // Function to check if a number // is a substring of other or not bool issubstring(string str2, string rep1) { int M = str2.length(); int N = rep1.length(); // Check for substring from starting // from i'th index of main string for ( int i = 0; i <= N - M; i++) { int j; // For current index i, // check for pattern match for (j = 0; j < M; j++) if (rep1[i + j] != str2[j]) break ; if (j == M) // pattern matched return true ; } return false ; // not a substring } // Function to find Minimum number of times A // has to be repeated such that B is a substring of it int Min_repetation(string A, string B) { // To store minimum number of repetitions int ans = 1; // To store repeated string string S = A; // Until size of S is less than B while (S.size() < B.size()) { S += A; ans++; } // ans times repetition makes required answer if (issubstring(B, S)) return ans; // Add one more string of A if (issubstring(B, S+A)) return ans + 1; // If no such solution exists return -1; } // Driver code int main() { string A = "abcd" , B = "cdabcdab" ; // Function call cout << Min_repetation(A, B); return 0; } |
Java
// Java program to find minimum number // of times 'A' has to be repeated // such that 'B' is a substring of it class GFG { // Function to check if a number // is a substring of other or not static boolean issubstring(String str2, String rep1) { int M = str2.length(); int N = rep1.length(); // Check for substring from starting // from i'th index of main string for ( int i = 0 ; i <= N - M; i++) { int j; // For current index i, // check for pattern match for (j = 0 ; j < M; j++) if (rep1.charAt(i + j) != str2.charAt(j)) break ; if (j == M) // pattern matched return true ; } return false ; // not a substring } // Function to find Minimum number // of times 'A' has to be repeated // such that 'B' is a substring of it static int Min_repetation(String A, String B) { // To store minimum number of repetitions int ans = 1 ; // To store repeated string String S = A; // Until size of S is less than B while (S.length() < B.length()) { S += A; ans++; } // ans times repetition makes required answer if (issubstring(B, S)) return ans; // Add one more string of A if (issubstring(B, S + A)) return ans + 1 ; // If no such solution exists return - 1 ; } // Driver code public static void main(String[] args) { String A = "abcd" , B = "cdabcdab" ; // Function call System.out.println(Min_repetation(A, B)); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to find minimum number # of times 'A' has to be repeated # such that 'B' is a substring of it # Method to find Minimum number # of times 'A' has to be repeated # such that 'B' is a substring of it 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): # we are reiterating over A again and # again for each value of B # Resetting A pointer back to 0 as B # is not empty yet if k > = len_a: k = 0 count = count + 1 # Resetting A means count # needs to be increased if a[k] ! = b[j]: break k = k + 1 # k is iterating over A else : return count return - 1 # Driver Code A = 'abcd' B = 'cdabcdab' print (min_repetitions(A, B)) # This code is contributed by satycool |
C#
// C# program to find minimum number // of times 'A' has to be repeated // such that 'B' is a substring of it using System; class GFG { // Function to check if a number // is a substring of other or not static Boolean issubstring(String str2, String rep1) { int M = str2.Length; int N = rep1.Length; // Check for substring from starting // from i'th index of main string for ( int i = 0; i <= N - M; i++) { int j; // For current index i, // check for pattern match for (j = 0; j < M; j++) if (rep1[i + j] != str2[j]) break ; if (j == M) // pattern matched return true ; } return false ; // not a substring } // Function to find Minimum number // of times 'A' has to be repeated // such that 'B' is a substring of it static int Min_repetation(String A, String B) { // To store minimum number of repetitions int ans = 1; // To store repeated string String S = A; // Until size of S is less than B while (S.Length < B.Length) { S += A; ans++; } // ans times repetition makes required answer if (issubstring(B, S)) return ans; // Add one more string of A if (issubstring(B, S + A)) return ans + 1; // If no such solution exists return -1; } // Driver code public static void Main(String[] args) { String A = "abcd" , B = "cdabcdab" ; // Function call Console.WriteLine(Min_repetation(A, B)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to find Minimum number of times A // has to be repeated such that B is a substring of it // Function to check if a number // is a substring of other or not function issubstring(str2, rep1) { var M = str2.length; var N = rep1.length; // Check for substring from starting // from i'th index of main string for ( var i = 0; i <= N - M; i++) { var j; // For current index i, // check for pattern match for (j = 0; j < M; j++) if (rep1[i + j] != str2[j]) break ; if (j == M) // pattern matched return true ; } return false ; // not a substring } // Function to find Minimum number of times A // has to be repeated such that B is a substring of it function Min_repetation(A, B) { // To store minimum number of repetitions var ans = 1; // To store repeated string var S = A; // Until size of S is less than B while (S.length < B.length) { S += A; ans++; } // ans times repetition makes required answer if (issubstring(B, S)) return ans; // Add one more string of A if (issubstring(B, S+A)) return ans + 1; // If no such solution exists return -1; } // Driver code var A = "abcd" , B = "cdabcdab" ; // Function call document.write( Min_repetation(A, B)); </script> |
3
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
/*package whatever //do not write package name here */ 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, it means we have repeated the // string if (j == 0 ) ++count; k += 1 ; } if (found) return count; } return - 1 ; } public static void main(String[] args) { String A = "abcd" , B = "cdabcdab" ; // Function call System.out.println(repeatedStringMatch(A, B)); } } |
Python
# Python implementation of this approach 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 # Driver code A = "abcd" ; B = "cdabcdab" ; print (repeatedStringMatch(A, B)); # This code is contributed by shinjanpatra |
C#
// C# program to find minimum number // of times 'A' has to be repeated // such that 'B' is a substring of it 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; } // Driver code public static void Main(String[] args) { String A = "abcd" , B = "cdabcdab" ; // Function call Console.WriteLine(repeatedStringMatch(A, B)); } } // This code is contributed by Pushpesh Raj |
Javascript
<script> // JavaScript implementation of this approach 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; } // Driver code let A = "abcd" ; let B = "cdabcdab" ; document.write(repeatedStringMatch(A, B)); </script> // This code is contributed by shinjanpatra |
3
Time Complexity: O(N * M)
Auxiliary Space: O(1).
Contact Us