Smallest String consisting of a String S exactly K times as a Substring
Last Updated :
01 Nov, 2022
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 = “geeksforgeeks”, K = 3
Output: “geeksforgeeksforgeeksforgeeks”
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++
#include <bits/stdc++.h>
using namespace std;
int* 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;
}
string findString(string& s, int k)
{
int n = s.length();
int* lps = kmp(s);
string ans = "";
string suff
= s.substr(0, n - lps[n - 1]);
for (int i = 0; i < k - 1; ++i) {
ans += suff;
}
ans += s;
return ans;
}
int main()
{
int k = 3;
string s = "geeksforgeeks";
cout << findString(s, k) << endl;
}
|
Java
import java.util.*;
class GFG{
static 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;
}
static String findString(String s, int k)
{
int n = s.length();
int[] lps = kmp(s);
String ans = "";
String suff = s.substring(0, n - lps[n - 1]);
for(int i = 0; i < k - 1; ++i)
{
ans += suff;
}
ans += s;
return ans;
}
public static void main (String[] args)
{
int k = 3;
String s = "geeksforgeeks";
System.out.println(findString(s, k));
}
}
|
Python3
def 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
def findString(s, k):
n = len(s)
lps = kmp(s)
ans = ""
suff = s[0: n - lps[n - 1] : 1]
for i in range(k - 1):
ans += suff
ans += s
return ans
k = 3
s = "geeksforgeeks"
print(findString(s, k))
|
C#
using System;
class GFG{
static 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;
}
static string findString(string s, int k)
{
int n = s.Length;
int[] lps = kmp(s);
string ans = "";
string suff = s.Substring(0,
n - lps[n - 1]);
for(int i = 0; i < k - 1; ++i)
{
ans += suff;
}
ans += s;
return ans;
}
public static void Main (string[] args)
{
int k = 3;
string s = "geeksforgeeks";
Console.Write(findString(s, k));
}
}
|
Javascript
<script>
function 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 findString(s, k)
{
var n = s.length;
var lps = kmp(s);
var ans = "";
var suff = s.substr(0, n - lps[n - 1]);
for (var i = 0; i < k - 1; ++i) {
ans += suff;
}
ans += s;
return ans;
}
var k = 3;
var s = "geeksforgeeks";
document.write(findString(s, k));
</script>
|
Output
geeksforgeeksforgeeksforgeeks
Time Complexity: O( |S| ), where S is the given string
Auxiliary Space: O( |S| )
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...