Intuition
We need to observe the fact that string B can be obtained as a substring of a string generated by definite repetitions of A, or it cannot be obtained at all.
The number of times A needs to be repeated can be calculated by division of the size of string B by the size of A, i.e.
count = M / N
where count = number of repetitions,
M = size of string B and
N = size of string A
But we can have any suffix of the string A as the prefix of string B, and vice versa. So to balance either case, we need to increase the count of repetition of string A by two: one to include as the prefix and one to include as the suffix. Thus the maximum possible repetitions of A to find string B as a substring is
count = M / N + 2
Approach
As discussed above, the maximum possible repetitions of A to find string B as a substring is (M / N) + 2, but we are asked to find the minimum number of repetitions, so we can start checking with the minimum required repetitions, i.e., M / N, then we can increase the count of repetitions unless we find B as a substring. If this count exceeds M / N +2, then we can conclude that string B cannot be found as a substring of a string generated by the repetitions of string A.
The implementation of the above approach can be understood by the below program.
Program
// Program to find minimum repetitions of string A to find string B as its substring.
#include <iostream>
using namespace std;
// Function to find minimum repetitions.
int minRepetitions(string &A, string &B)
{
// Storing the length of strings.
int N = A.length(), M = B.length();
// Variable to store count of string A and maximum allowed repetitions.
int count = M / N, mCount = M / N + 2;
// Temporary string to store the repetitions of string ‘A’.
string tmp = "";
for (int i = 0; i < count; i++)
tmp += A;
// Increasing the repetitions until ‘B’ is found as a substring.
while (count <= mCount)
{
// Checking if B is present as a substring.
if (tmp.find(B) != string::npos)
return count;
// Repeating the number of A.
tmp += A;
// Increasing the actual count.
count++;
}
// If not possible, returning -1 finally.
return -1;
}
// Main Function.
int main()
{
// Input the strings.
string A, B;
cin >> A >> B;
// Storing the final answer.
int ans = minRepetitions(A, B);
// Final output.
if (ans == -1)
cout << "Not Possible";
else
cout << "Minimum Repetitions Required: " << ans;
return 0;
}
You can also try this code with Online C++ Compiler
Example
Input
abbwe
weabbwea
Output
Minimum Repetitions Required: 3
Also check out - Substr C++
Complexity Analysis
Time Complexity: O(M), where ‘M’ is the size of string B.
Explanation: The for loop used to generate the string ‘tmp’, is running for (M / N) times, where in each repetition, adding the string A to ‘tmp’ takes O(N) time. Also, the later while loop takes no more than O(M) time to process the repetitions.
So the total time taken by the program will be O(N x (M / N)) time which is equal to O(M) time.
Auxiliary Space: O(M), where ‘M’ is the size of string B.
Explanation: The string ‘tmp’, used to store the repetitions of string A, stores N characters a total of (M / N) times, evaluating to O(M).
Also see, Morris Traversal for Inorder.and Rabin Karp Algorithm
Key Takeaways
The above blog discussed an interesting question that involves the concepts of strings and substrings. ‘Minimum repetitions of string A, to generate string B as its substring’ is also an important problem from the interview point of view, where you can be tested for such concepts instantaneously.
Check out this problem - Longest String Chain
If you want to learn more about such problems, head over to our library section for many such interesting blogs. Keep learning.
Happy Coding!
242+ registered 
