Número máximo de veces que una string determinada debe concatenarse para formar una substring de otra string

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)

Publicación traducida automáticamente

Artículo escrito por garry133 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *