Given two strings S1 and S2 of length N and M respectively, the task is to find the maximum value of times the string S2 needs to be concatenated, such that it is a substring of the string S1.
Examples:
Input: S1 = “ababc”, S2 = “ab”
Output: 2
Explanation: After concatenating S2 exactly twice, the string modifies to “abab”. Therefore, string “abab” is a substring of “ababc”. Therefore, the result is 2.Input: S1 = “ababc”, S2 = “ba”
Output: 1
Explanation: String “ba” is already a substring of “ababc”. Therefore, the result is 1.
Approach: To solve the given problem, the idea to use the KMP algorithm. Follow the steps below to solve the problem:
- Initialize a variable, say ans, to store the maximum value K such that concatenating S2 K times form a substring of the string S1.
- Initialize a string curWord and copy the contents of S2 in curWord.
- Store the maximum number of times a string can occur as numWords = N / M.
- Traverse the string over the indices [0, numWords – 1] and perform the following steps:
- If the value of curWord is found in string S1, then increment ans by 1 and concatenate curWord with the word.
- Otherwise, break out of the loop.
- After the above steps, print the value of ans as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find lps[] for given// pattern pat[0..M-1]void computeLPSArray(string pat, int M, int* lps){ // Length of the previous // longest prefix suffix int len = 0; // lps[0] is always 0 lps[0] = 0; // Iterate string to calculate lps[i] int i = 1; while (i < M) { // If the current character // of the pattern matches if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } // Otherwise else { if (len != 0) { len = lps[len - 1]; } // Otherwise else { lps[i] = 0; i++; } } }}// Function to implement KMP algorithmint KMPSearch(string pat, string txt){ int M = pat.size(); int N = txt.size(); // Stores the longest prefix and // suffix values for pattern int lps[M]; // Preprocess the pattern and // find the lps[] array computeLPSArray(pat, M, lps); // Index for txt[] int i = 0; // Index for pat[] int j = 0; while (i < N) { if (pat[j] == txt[i]) { j++; i++; } // If pattern is found return 1 if (j == M) { return 1; j = lps[j - 1]; } // Mismatch after j matches else if (i < N && pat[j] != txt[i]) { // Don't match lps[0, lps[j - 1]] // characters they will // match anyway if (j != 0) j = lps[j - 1]; else i = i + 1; } } // Return 0 if the pattern is not found return 0;}// Function to find the maximum value// K for which string S2 concatenated// K times is a substring of string S1void maxRepeating(string seq, string word){ // Store the required maximum number int resCount = 0; // Create a temporary string to store // string word string curWord = word; // Store the maximum number of times // string S2 can occur in string S1 int numWords = seq.length() / word.length(); // Traverse in range[0, numWords-1] for (int i = 0; i < numWords; i++) { // If curWord is found in sequence if (KMPSearch(curWord, seq)) { // Concatenate word to curWord curWord += word; // Increment resCount by 1 resCount++; } // Otherwise break the loop else break; } // Print the answer cout << resCount;}// Driver Codeint main(){ string S1 = "ababc", S2 = "ab"; // Function Call maxRepeating(S1, S2); return 0;} |
Java
// Java program for the above approachclass GFG{ // Function to find lps[] for given // pattern pat[0..M-1] static void computeLPSArray(String pat, int M, int []lps) { // Length of the previous // longest prefix suffix int len = 0; // lps[0] is always 0 lps[0] = 0; // Iterate string to calculate lps[i] int i = 1; while (i < M) { // If the current character // of the pattern matches if (pat.charAt(i) == pat.charAt(len)) { len++; lps[i] = len; i++; } // Otherwise else { if (len != 0) { len = lps[len - 1]; } // Otherwise else { lps[i] = 0; i++; } } } } // Function to implement KMP algorithm static int KMPSearch(String pat, String txt) { int M = pat.length(); int N = txt.length(); // Stores the longest prefix and // suffix values for pattern int lps[] = new int[M]; // Preprocess the pattern and // find the lps[] array computeLPSArray(pat, M, lps); // Index for txt[] int i = 0; // Index for pat[] int j = 0; while (i < N) { if (pat.charAt(j) == txt.charAt(i)) { j++; i++; } // If pattern is found return 1 if (j == M) { return 1; //j = lps[j - 1]; } // Mismatch after j matches else if (i < N && pat.charAt(j) != txt.charAt(i)) { // Don't match lps[0, lps[j - 1]] // characters they will // match anyway if (j != 0) j = lps[j - 1]; else i = i + 1; } } // Return 0 if the pattern is not found return 0; } // Function to find the maximum value // K for which string S2 concatenated // K times is a substring of string S1 static void maxRepeating(String seq, String word) { // Store the required maximum number int resCount = 0; // Create a temporary string to store // string word String curWord = word; // Store the maximum number of times // string S2 can occur in string S1 int numWords = seq.length() / word.length(); // Traverse in range[0, numWords-1] for (int i = 0; i < numWords; i++) { // If curWord is found in sequence if (KMPSearch(curWord, seq) == 1) { // Concatenate word to curWord curWord += word; // Increment resCount by 1 resCount++; } // Otherwise break the loop else break; } // Print the answer System.out.print(resCount); } // Driver Code public static void main (String[] args) { String S1 = "ababc", S2 = "ab"; // Function Call maxRepeating(S1, S2); }}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approach# Function to find lps[] for given# pattern pat[0..M-1]def computeLPSArray(pat, M, lps): # Length of the previous # longest prefix suffix lenn = 0 # lps[0] is always 0 lps[0] = 0 # Iterate string to calculate lps[i] i = 1 while (i < M): # If the current character # of the pattern matches if (pat[i] == pat[lenn]): lenn += 1 lps[i] = lenn i += 1 # Otherwise else: if (lenn != 0): lenn = lps[lenn - 1] # Otherwise else: lps[i] = 0 i += 1# Function to implement KMP algorithmdef KMPSearch(pat, txt): M = len(pat) N = len(txt) # Stores the longest prefix and # suffix values for pattern lps = [0 for i in range(M)] # Preprocess the pattern and # find the lps[] array computeLPSArray(pat, M, lps) # Index for txt[] i = 0 # Index for pat[] j = 0 while (i < N): if (pat[j] == txt[i]): j += 1 i += 1 # If pattern is found return 1 if (j == M): return 1 j = lps[j - 1] # Mismatch after j matches elif (i < N and pat[j] != txt[i]): # Don't match lps[0, lps[j - 1]] # characters they will # match anyway if (j != 0): j = lps[j - 1] else: i = i + 1 # Return 0 if the pattern is not found return 0# Function to find the maximum value# K for which S2 concatenated# K times is a subof S1def maxRepeating(seq, word): # Store the required maximum number resCount = 0 # Create a temporary to store # word curWord = word # Store the maximum number of times # S2 can occur in S1 numWords = len(seq) // len(word) # Traverse in range[0, numWords-1] for i in range(numWords): # If curWord is found in sequence if (KMPSearch(curWord, seq)): # Concatenate word to curWord curWord += word # Increment resCount by 1 resCount += 1 # Otherwise break the loop else: break # Print the answer print(resCount)# Driver Codeif __name__ == '__main__': S1,S2 = "ababc","ab" # Function Call maxRepeating(S1, S2)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find lps[] for given // pattern pat[0..M-1] static void computeLPSArray(String pat, int M, int []lps) { // Length of the previous // longest prefix suffix int len = 0; // lps[0] is always 0 lps[0] = 0; // Iterate string to calculate lps[i] int i = 1; while (i < M) { // If the current character // of the pattern matches if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } // Otherwise else { if (len != 0) { len = lps[len - 1]; } // Otherwise else { lps[i] = 0; i++; } } } } // Function to implement KMP algorithm static int KMPSearch(String pat, String txt) { int M = pat.Length; int N = txt.Length; // Stores the longest prefix and // suffix values for pattern int []lps = new int[M]; // Preprocess the pattern and // find the lps[] array computeLPSArray(pat, M, lps); // Index for txt[] int i = 0; // Index for pat[] int j = 0; while (i < N) { if (pat[j] == txt[i]) { j++; i++; } // If pattern is found return 1 if (j == M) { return 1; //j = lps[j - 1]; } // Mismatch after j matches else if (i < N && pat[j] != txt[i]) { // Don't match lps[0, lps[j - 1]] // characters they will // match anyway if (j != 0) j = lps[j - 1]; else i = i + 1; } } // Return 0 if the pattern is not found return 0; } // Function to find the maximum value // K for which string S2 concatenated // K times is a substring of string S1 static void maxRepeating(String seq, String word) { // Store the required maximum number int resCount = 0; // Create a temporary string to store // string word String curWord = word; // Store the maximum number of times // string S2 can occur in string S1 int numWords = seq.Length / word.Length; // Traverse in range[0, numWords-1] for (int i = 0; i < numWords; i++) { // If curWord is found in sequence if (KMPSearch(curWord, seq) == 1) { // Concatenate word to curWord curWord += word; // Increment resCount by 1 resCount++; } // Otherwise break the loop else break; } // Print the answer Console.Write(resCount); } // Driver Code public static void Main(String[] args) { String S1 = "ababc", S2 = "ab"; // Function Call maxRepeating(S1, S2); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program for the above approach// Function to find lps[] for given// pattern pat[0..M-1]function computeLPSArray(pat, M, lps){ // Length of the previous // longest prefix suffix var len = 0; // lps[0] is always 0 lps[0] = 0; // Iterate string to calculate lps[i] var i = 1; while (i < M) { // If the current character // of the pattern matches if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } // Otherwise else { if (len != 0) { len = lps[len - 1]; } // Otherwise else { lps[i] = 0; i++; } } }}// Function to implement KMP algorithmfunction KMPSearch(pat, txt){ var M = pat.length; var N = txt.length; // Stores the longest prefix and // suffix values for pattern var lps = Array(M); // Preprocess the pattern and // find the lps[] array computeLPSArray(pat, M, lps); // Index for txt[] var i = 0; // Index for pat[] var j = 0; while (i < N) { if (pat[j] == txt[i]) { j++; i++; } // If pattern is found return 1 if (j == M) { return 1; j = lps[j - 1]; } // Mismatch after j matches else if (i < N && pat[j] != txt[i]) { // Don't match lps[0, lps[j - 1]] // characters they will // match anyway if (j != 0) j = lps[j - 1]; else i = i + 1; } } // Return 0 if the pattern is not found return 0;}// Function to find the maximum value// K for which string S2 concatenated// K times is a substring of string S1function maxRepeating(seq, word){ // Store the required maximum number var resCount = 0; // Create a temporary string to store // string word var curWord = word; // Store the maximum number of times // string S2 can occur in string S1 var numWords = seq.length / word.length; // Traverse in range[0, numWords-1] for (var i = 0; i < numWords; i++) { // If curWord is found in sequence if (KMPSearch(curWord, seq)) { // Concatenate word to curWord curWord += word; // Increment resCount by 1 resCount++; } // Otherwise break the loop else break; } // Print the answer document.write( resCount);}// Driver Codevar S1 = "ababc", S2 = "ab";// Function CallmaxRepeating(S1, S2);</script> |
Output:
2
Time Complexity: O(N2)
Auxiliary Space: O(M)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!