Dada una string S de longitud N y un número entero K , encuentre la string de longitud más pequeña que contenga la string S como una substring exactamente K veces.
Ejemplos:
Entrada: S = “abba”, K = 3 Salida: abbabbabba Explicación: La string “abba” aparece K veces en la string abbabbabba, es decir { abba bbabba, abb abba bba, abbabb abba } Entrada: S = “geeksforgeeks”, K = 3 Salida: «geeksforgeeksforgeeksforgeeks»
Enfoque: Para optimizar el enfoque anterior, encuentre el Prefijo propio más largo , que también es un sufijo para la string dada S , y luego genere una substring de S que excluya el prefijo común más largo y agregue esta substring a la respuesta exactamente K – 1 veces a la string original. Siga los pasos a continuación para resolver el problema:
- Encuentre la longitud del prefijo apropiado más largo usando el algoritmo KMP .
- Agregue la substring S.substring(N-lps[N-1]) a S, exactamente K-1 veces.
- Imprime la respuesta.
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// KMP algorithm
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;
}
// Function to return the required string
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.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 Code
int main()
{
int k = 3;
string s = "geeksforgeeks";
cout << findString(s, k) << endl;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// KMP algorithm
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;
}
// Function to return the required string
static 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 code
public static void main (String[] args)
{
int k = 3;
String s = "geeksforgeeks";
System.out.println(findString(s, k));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach # KMP algorithm 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 # Function to return the required string def 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 code k = 3 s = "geeksforgeeks" print(findString(s, k)) # This code is contributed by divyeshrabadiya07
C#
// C# program to implement
// the above approach
using System;
class GFG{
// KMP algorithm
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;
}
// Function to return the required string
static 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 code
public static void Main (string[] args)
{
int k = 3;
string s = "geeksforgeeks";
Console.Write(findString(s, k));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// JavaScript Program to implement
// the above approach
// KMP algorithm
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 to return the required string
function 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 Code
var k = 3;
var s = "geeksforgeeks";
document.write(findString(s, k));
//This code is contributed by phasing17
</script>
Producción
geeksforgeeksforgeeksforgeeks