Compruebe si el recuento de substrings en S con la string S1 como prefijo y S2 como sufijo es igual al que tiene S2 como prefijo y S1 como sufijo

Dadas tres strings S , S1 y S2 , la tarea es verificar si la cantidad de substrings que comienzan y terminan con S1 y S2 es igual a la cantidad de substrings que comienzan y terminan con S2 y S1 o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .

Ejemplos:

Entrada: S = “holamundomundoholamundo”, S1 = “hola”, S2 = “mundo”
Salida: No
Explicación:
Las substrings que comienzan con S1 (= “hola”) y terminan con S2 (= “mundo”) son {“holamundo ”, “holamundomundo”, “holamundomundoholamundo”, “holamundo”}. 
Por lo tanto, el recuento total es 4.
Las substrings que comienzan con S2 (= “mundo”) y terminan con S1(= “hola”) son {“mundomundohola”, “mundohola”}.
Por lo tanto, el conteo total es 2.
Por lo tanto, los dos conteos anteriores no son iguales.

Entrada: S = «abrircerrarabrircerrarabrir», S1 = «abrir», S2 = «cerrar»
Salida: Sí

Enfoque: siga los pasos a continuación para resolver el problema:

• Almacene la longitud de las strings S , S1 y S2 en variables, digamos N , N1 y N2 respectivamente.
• Inicialice una variable, digamos count , para almacenar el número de ocurrencias de la substring S1 en la string S .
• Inicialice una variable, digamos ans , para almacenar substrings que comiencen y terminen con S1 y S2 respectivamente.
• Atraviese la string S dada y realice los siguientes pasos:
  • Almacene la substring de la string S que comienza en el índice i de tamaño N1 en el prefijo de string .
  • Almacene la substring de la string S que comienza en el índice i de tamaño N2 en el sufijo de string .
  • Si el prefijo es el mismo que el de la string S1 , incremente el valor de count en 1 .
  • Si el sufijo es el mismo que la string S2 , incremente el valor de ans por conteo .
• Use los pasos anteriores para encontrar la cantidad de substrings que comienzan y terminan con S2 y S1 respectivamente. Almacene el conteo obtenido en la variable digamos ans2 .
• Si se encuentra que los valores de ans y ans2 son iguales, imprima «Sí» . De lo contrario, escriba “No” .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count number of
// substrings that starts with
// string S1 and ends with string S2
int countSubstrings(string S, string S1,
                    string S2)
{
    // Stores the length of each string
    int N = S.length();
    int N1 = S1.length();
    int N2 = S2.length();
 
    // Stores the count of prefixes
    // as S1 and suffixes as S2
    int count = 0, totalcount = 0;
 
    // Traverse string S
    for (int i = 0; i < N; i++) {
 
        // Find the prefix at index i
        string prefix = S.substr(i, N1);
 
        // Find the suffix at index i
        string suffix = S.substr(i, N2);
 
        // If the prefix is S1
        if (S1 == prefix)
            count++;
 
        // If the suffix is S2
        if (S2 == suffix)
            totalcount += count;
    }
 
    // Return the count of substrings
    return totalcount;
}
 
// Function to check if the number of
// substrings starts with S1 and ends
// with S2 and vice-versa is same or not
void checkSubstrings(string S, string S1,
                     string S2)
{
 
    // Count the number of substrings
    int x = countSubstrings(S, S1, S2);
    int y = countSubstrings(S, S2, S1);
 
    // Print the result
    if (x == y)
        cout << "Yes";
    else
        cout << "No";
}
 
// Driver Code
int main()
{
    string S = "opencloseopencloseopen";
    string S1 = "open";
    string S2 = "close";
    checkSubstrings(S, S1, S2);
 
    return 0;
}

// Java program for the above approach
class GFG{
 
// Function to count number of
// substrings that starts with
// string S1 and ends with string S2
static int countSubstrings(String S, String S1,
                           String S2)
{
     
    // Stores the length of each string
    int N = S.length();
    int N1 = S1.length();
    int N2 = S2.length();
 
    // Stores the count of prefixes
    // as S1 and suffixes as S2
    int count = 0, totalcount = 0;
 
    // Traverse string S
    for(int i = 0; i < N; i++)
    {
         
        // Find the prefix at index i
        String prefix = S.substring(
            i, (i + N1 < N) ? (i + N1) : N);
 
        // Find the suffix at index i
        String suffix = S.substring(
            i, (i + N2 < N) ? (i + N2) : N);
 
        // If the prefix is S1
        if (S1.equals(prefix))
            count++;
 
        // If the suffix is S2
        if (S2.equals(suffix))
            totalcount += count;
    }
 
    // Return the count of substrings
    return totalcount;
}
 
// Function to check if the number of
// substrings starts with S1 and ends
// with S2 and vice-versa is same or not
static void checkSubstrings(String S, String S1,
                            String S2)
{
 
    // Count the number of substrings
    int x = countSubstrings(S, S1, S2);
 
    int y = countSubstrings(S, S2, S1);
 
    // Print the result
    if (x == y)
        System.out.println("Yes");
    else
        System.out.println("No");
}
 
// Driver Code
public static void main(String[] args)
{
    String S = "opencloseopencloseopen";
    String S1 = "open";
    String S2 = "close";
     
    checkSubstrings(S, S1, S2);
}
}
 
// This code is contributed by abhinavjain194

# Python3 program for the above approach
 
# Function to count number of
# substrings that starts with
# string S1 and ends with string S2
def countSubstrings(S, S1, S2):
     
    # Stores the length of each string
    N = len(S)
    N1 = len(S1)
    N2 = len(S2)
     
    # Stores the count of prefixes
    # as S1 and suffixes as S2
    count = 0
    totalcount = 0
     
    # Traverse string S
    for i in range(N):
         
        # Find the prefix at index i
        prefix = S[i: (i + N1) if (i + N1 < N) else N]
         
        # Find the suffix at index i
        suffix = S[i: (i + N2) if (i + N2 < N) else N]
         
        # If the prefix is S1
        if S1 == prefix:
            count += 1
             
        # If the suffix is S2
        if S2 == suffix:
            totalcount += count
             
    # Return the count of substrings
    return totalcount
 
# Function to check if the number of
# substrings starts with S1 and ends
# with S2 and vice-versa is same or not
def checkSubstrings(S, S1, S2):
     
    x = countSubstrings(S, S1, S2)
    y = countSubstrings(S, S2, S1)
 
    if x == y:
        print("Yes")
    else:
        print("No")
 
# Driver code
S = "opencloseopencloseopen"
S1 = "open"
S2 = "close"
 
checkSubstrings(S, S1, S2)
 
# This code is contributed by abhinavjain194

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count number of
// substrings that starts with
// string S1 and ends with string S2
static int countSubstrings(string S, string S1,
                           string S2)
{
     
    // Stores the length of each string
    int N = S.Length;
    int N1 = S1.Length;
    int N2 = S2.Length;
 
    // Stores the count of prefixes
    // as S1 and suffixes as S2
    int count = 0, totalcount = 0;
 
    // Traverse string S
    for(int i = 0; i < N; i++)
    {
         
        // Find the prefix at index i
        String prefix = S.Substring(
            i, (i + N1 < N) ? N1 : (N - i));
 
        // Find the suffix at index i
        String suffix = S.Substring(
            i, (i + N2 < N) ? N2 : (N - i));
 
        // If the prefix is S1
        if (S1.Equals(prefix))
            count++;
 
        // If the suffix is S2
        if (S2.Equals(suffix))
            totalcount += count;
    }
 
    // Return the count of substrings
    return totalcount;
}
 
// Function to check if the number of
// substrings starts with S1 and ends
// with S2 and vice-versa is same or not
static void checkSubstrings(string S, string S1,
                            string S2)
{
 
    // Count the number of substrings
    int x = countSubstrings(S, S1, S2);
 
    int y = countSubstrings(S, S2, S1);
 
    // Print the result
    if (x == y)
        Console.Write("Yes");
    else
        Console.Write("No");
}
 
// Driver code
static void Main()
{
    string S = "opencloseopencloseopen";
    string S1 = "open";
    string S2 = "close";
     
    checkSubstrings(S, S1, S2);
}
}
 
// This code is contributed by abhinavjain194

<script>
// Javascript program for the above approach
 
// Function to count number of
// substrings that starts with
// string S1 and ends with string S2
function countSubstrings(S, S1, S2)
{
 
    // Stores the length of each string
    let N = S.length;
    let N1 = S1.length;
    let N2 = S2.length;
 
    // Stores the count of prefixes
    // as S1 and suffixes as S2
    let count = 0, totalcount = 0;
 
    // Traverse string S
    for (let i = 0; i < N; i++) {
 
        // Find the prefix at index i
        let prefix = S.substr(i, N1);
 
        // Find the suffix at index i
        let suffix = S.substr(i, N2);
 
        // If the prefix is S1
        if (S1 == prefix)
            count++;
 
        // If the suffix is S2
        if (S2 == suffix)
            totalcount += count;
    }
 
    // Return the count of substrings
    return totalcount;
}
 
// Function to check if the number of
// substrings starts with S1 and ends
// with S2 and vice-versa is same or not
function checkSubstrings(S, S1, S2)
{
 
    // Count the number of substrings
    let x = countSubstrings(S, S1, S2);
    let y = countSubstrings(S, S2, S1);
 
    // Print the result
    if (x == y)
        document.write("Yes");
    else
        document.write("No");
}
 
// Driver Code
    let S = "opencloseopencloseopen";
    let S1 = "open";
    let S2 = "close";
    checkSubstrings(S, S1, S2);
 
// This code is contributed by gfgking
</script>

Yes

Complejidad de tiempo: O(N * (N1 + N2)), donde N, N1 y N2 son la longitud de las strings S, S1 y S2 respectivamente.
Espacio Auxiliar: O(1)