Given a string S of length N and integer K, find the smallest length string which contains the string S as a sub string exactly K times.
Examples:
Input: S = “abba”, K = 3
Output: abbabbabba
Explanation: The string “abba” occurs K times in the string abbabbabba, i.e. {abbabbabba, abbabbabba, abbabbabba}Input: S = “neveropen”, K = 3
Output: “neveropenforneveropen”
Approach: To optimize the above approach, find the Longest Proper Prefix which is also a suffix for the given string S, and then generate a substring of S excluding the longest common prefix and add this substring to the answer exactly K – 1 times to the original string. Follow the below steps to solve the problem:
- Find the length of the longest proper prefix using KMP algorithm.
- Append substring S.substring(N-lps[N-1]) to S, exactly K-1 times.
- Print the answer.
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// KMP algorithmint* kmp(string& s){ int n = s.size(); int* lps = new int[n]; lps[0] = 0; int i = 1, len = 0; while (i < n) { if (s[i] == s[len]) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } return lps;}// Function to return the required stringstring findString(string& s, int k){ int n = s.length(); // Finding the longest proper prefix // which is also suffix int* lps = kmp(s); // ans string string ans = ""; string suff = s.substr(0, n - lps[n - 1]); for (int i = 0; i < k - 1; ++i) { // Update ans appending the // substring K - 1 times ans += suff; } // Append the original string ans += s; // Returning min length string // which contain exactly k // substring of given string return ans;}// Driver Codeint main(){ int k = 3; string s = "neveropen"; cout << findString(s, k) << endl;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ // KMP algorithmstatic int[] kmp(String s){ int n = s.length(); int[] lps = new int[n]; lps[0] = 0; int i = 1, len = 0; while (i < n) { if (s.charAt(i) == s.charAt(len)) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } return lps;}// Function to return the required stringstatic String findString(String s, int k){ int n = s.length(); // Finding the longest proper prefix // which is also suffix int[] lps = kmp(s); // ans string String ans = ""; String suff = s.substring(0, n - lps[n - 1]); for(int i = 0; i < k - 1; ++i) { // Update ans appending the // substring K - 1 times ans += suff; } // Append the original string ans += s; // Returning min length string // which contain exactly k // substring of given string return ans;}// Driver codepublic static void main (String[] args){ int k = 3; String s = "neveropen"; System.out.println(findString(s, k));}}// This code is contributed by offbeat |
Python3
# Python3 program to implement# the above approach# KMP algorithmdef kmp(s): n = len(s) lps = [None] * n lps[0] = 0 i, Len = 1, 0 while (i < n): if (s[i] == s[Len]): Len += 1 lps[i] = Len i += 1 else: if (Len != 0): Len = lps[Len - 1] else: lps[i] = 0 i += 1 return lps # Function to return the required stringdef findString(s, k): n = len(s) # Finding the longest proper prefix # which is also suffix lps = kmp(s) # ans string ans = "" suff = s[0: n - lps[n - 1] : 1] for i in range(k - 1): # Update ans appending the # substring K - 1 times ans += suff # Append the original string ans += s # Returning min length string # which contain exactly k # substring of given string return ans# Driver codek = 3 s = "neveropen" print(findString(s, k))# This code is contributed by divyeshrabadiya07 |
C#
// C# program to implement// the above approachusing System;class GFG{ // KMP algorithmstatic int[] kmp(string s){ int n = s.Length; int[] lps = new int[n]; lps[0] = 0; int i = 1, len = 0; while (i < n) { if (s[i] == s[len]) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } return lps;}// Function to return the required stringstatic string findString(string s, int k){ int n = s.Length; // Finding the longest proper prefix // which is also suffix int[] lps = kmp(s); // ans string string ans = ""; string suff = s.Substring(0, n - lps[n - 1]); for(int i = 0; i < k - 1; ++i) { // Update ans appending the // substring K - 1 times ans += suff; } // Append the original string ans += s; // Returning min length string // which contain exactly k // substring of given string return ans;}// Driver codepublic static void Main (string[] args){ int k = 3; string s = "neveropen"; Console.Write(findString(s, k));}}// This code is contributed by rutvik_56 |
Javascript
<script>// JavaScript Program to implement// the above approach// KMP algorithmfunction kmp(s){ var n = s.length; var lps = new Array(n); lps[0] = 0; var i = 1; var len = 0; while (i < n) { if (s[i] == s[len]) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } return lps;}// Function to return the required stringfunction findString(s, k){ var n = s.length; // Finding the longest proper prefix // which is also suffix var lps = kmp(s); // ans string var ans = ""; var suff = s.substr(0, n - lps[n - 1]); for (var i = 0; i < k - 1; ++i) { // Update ans appending the // substring K - 1 times ans += suff; } // Append the original string ans += s; // Returning min length string // which contain exactly k // substring of given string return ans;}// Driver Codevar k = 3;var s = "neveropen";document.write(findString(s, k));//This code is contributed by phasing17</script> |
Output
neveropenforneveropen
Time Complexity: O( |S| ), where S is the given string
Auxiliary Space: O( |S| )
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!
… [Trackback]
[…] There you can find 81406 more Information on that Topic: geeksforgeeks.org/smallest-string-consisting-of-a-string-s-exactly-k-times-as-a-substring/ […]