Dadas dos strings S1 y S2 de longitud N y M respectivamente, la tarea es encontrar el valor máximo de veces que la string S2 debe concatenarse, de modo que sea una substring de la string S1 .
Ejemplos:
Entrada: S1 = “ababc”, S2 = “ab”
Salida: 2
Explicación: Después de concatenar S2 exactamente dos veces, la string se modifica a “abab”. Por lo tanto, la string «abab» es una substring de «ababc». Por lo tanto, el resultado es 2.Entrada: S1 = “ababc”, S2 = “ba”
Salida: 1
Explicación: La string “ba” ya es una substring de “ababc”. Por lo tanto, el resultado es 1.
Enfoque: Para resolver el problema dado, la idea de utilizar el algoritmo KMP . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans , para almacenar el valor máximo K tal que concatenando S2 K veces forme una substring de la string S1 .
- Inicialice una string curWord y copie el contenido de S2 en curWord .
- Almacene el número máximo de veces que puede aparecer una string como numWords = N / M .
- Recorra la string sobre los índices [0, numWords – 1] y realice los siguientes pasos:
- Si el valor de curWord se encuentra en la string S1 , incremente ans en 1 y concatene curWord con la palabra .
- De lo contrario, sal del bucle .
- Después de los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
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 algorithm
int 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 S1
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)) {
// Concatenate word to curWord
curWord += word;
// Increment resCount by 1
resCount++;
}
// Otherwise break the loop
else
break;
}
// Print the answer
cout << resCount;
}
// Driver Code
int main()
{
string S1 = "ababc", S2 = "ab";
// Function Call
maxRepeating(S1, S2);
return 0;
}
Java
// Java program for the above approach
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.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 algorithm def 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 S1 def 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 Code if __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 approach
using 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 algorithm
function 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 S1
function 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 Code
var S1 = "ababc", S2 = "ab";
// Function Call
maxRepeating(S1, S2);
</script>
Producción:
2
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(M)