Cuente los pares de substrings de una string S de modo que S1 no ocurra después de S2 en cada par

Dadas tres strings str , str1 y str2 , la tarea es contar el número de pares de ocurrencias de str1 y str2 como una substring en la string str de modo que en cada par, el índice inicial de str1 sea menor o igual que str2 .

Ejemplos:

Entrada: str = “geeksforgeeksfor”, str1 = “geeks”, str2 = “for” 
Salida: 3 
Explicación: 
Los índices iniciales de str1 son { 0, 8 } 
Los índices iniciales de str2 son { 5, 13 } 
Posibles pares tales que el índice inicial de str1 menores o iguales a str2 son { (0, 5), (0, 13), (8, 13) } 
Por lo tanto, la salida requerida es 3.

Entrada: str = «geeksforgeeks», str1 = «geek», str2 = «para» 
Salida: 1

Enfoque: La idea es encontrar los índices iniciales de la substring str2 en la string str y en cada índice inicial de la string str2 incrementar el conteo de pares por el conteo de índices iniciales de str1 hasta el i ^-ésimo índice de str . Finalmente, imprima el conteo total de pares obtenidos. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos cntPairs , para almacenar el recuento de pares de str1 y str2 de modo que el índice inicial de str1 sea menor o igual que str2 .
• Inicialice una variable, digamos cntStr1 , para almacenar el conteo de substring , str1 en str cuyo índice de inicio es menor o igual que i .
• Iterar sobre el rango [0, N – 1] . Para cada i ^-ésimo índice de la string str , compruebe si la substring str1 existe en la string str cuyo índice inicial es igual a i o no. Si se determina que es cierto, entonces incremente el valor de cntStr1 en 1 .
• Para cada i ^-ésimo índice, verifique si la substring str2 está presente en la string cuyo índice inicial es igual a i o no. Si se encuentra que es cierto, entonces incremente el valor de cntPairs por cntStr1 .
• Finalmente, imprima el valor de cntPairs .

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

// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of pairs of str1
// and str2 in str such that starting index of
// str1 less than or equal to str2
int CountSubstring(string str, string str1, string str2)
{
 
    // Stores count of pairs of str1 and str2
    // such that the start index of str1 is
    // less than or equal to str2
    int cntPairs = 0;
 
    // Stores count of substring str1 in
    // str whose start index is up to i
    int cntStr1 = 0;
 
    // Iterate over the range [0, N -1]
    for (int i = 0; i < str.length(); i++) {
 
        // If substring str1 whose
        // start index is i
        if (str.substr(i, str1.length())
            == str1) {
 
            // Update cntStr1
            cntStr1++;
        }
 
        // If substring str2 whose
        // start index is i
        else if (str.substr(i, str2.length())
                 == str2) {
 
            // Update cntPairs
            cntPairs += cntStr1;
        }
    }
 
    return cntPairs;
}
 
// Driver Code
int main()
{
 
    string str = "geeksforgeeksfor";
    string str1 = "geeks", str2 = "for";
 
    cout << CountSubstring(str, str1, str2);
 
    return 0;
}

// Java program to implement
// the above approach
public class GFG {
 
    // Driver Code
    public static void main(String[] args)
    {
        String str = new String("geeksforgeeksfor");
        String str1 = new String("geeks");
        String str2 = new String("for");
 
        System.out.println(CountSubstring(
            str, str1, str2));
    }
 
    // Function to find the count of pairs of str1
    // and str2 in str such that starting index of
    // str1 less than or equal to str2
    static int CountSubstring(String str,
                              String str1,
                              String str2)
    {
 
        // Stores count of pairs of str1 and str2
        // such that the start index of str1 is
        // less than or equal to str2
        int cntPairs = 0;
 
        // Stores count of substring str1 in
        // str whose start index is up to i
        int cntStr1 = 0;
 
        // Stores length of str
        int N = str.length();
 
        // Stores length of str1
        int s1 = str1.length();
 
        // Stores length of str2
        int s2 = str2.length();
 
        // Iterate over the range [0, N -1]
        for (int i = 0; i < N; i++) {
 
            // If substring str1 whose
            // starting index is i
            if (((i + s1) <= N)
                && (str.substring(
                        i, (i + s1)))
                           .compareTo(str1)
                       == 0) {
 
                // Update cntStr1
                cntStr1++;
            }
 
            // If substring str2 whose
            // starting index is i
            else if (((i + s2) <= N)
                     && (str.substring(
                             i, (i + s2)))
                                .compareTo(str2)
                            == 0) {
 
                // Update cntPairs
                cntPairs += cntStr1;
            }
        }
 
        return cntPairs;
    }
}

# Python3 program to implement
# the above approach
 
# Function to find the count of pairs of str1
# and str2 in str such that starting index of
# str1 less than or equal to str2
def CountSubstring(str, str1, str2):
     
    # Stores count of pairs of str1 and str2
    # such that the start index of str1 is
    # less than or equal to str2
    cntStr1 = 0
     
    # Stores count of substring str1 in
    # str whose start index is up to i
    cntPairs = 0
     
    # Iterate over the range [0, N -1]
    for i in range(len(str)):
         
        # If substring str1 whose
        # start index is i
        if str[i : i + len(str1)] == str1:
             
            # Update cntStr1
            cntStr1 += 1
             
        # If substring str2 whose
        # start index is i   
        elif str[i : i + len(str2)] == str2:
             
            # Update cntPairs
            cntPairs += cntStr1
     
    return cntPairs
     
# Driver Code
str = 'geeksforgeeksfor'
str1 = 'geeks'
str2 = 'for'       
        
print(CountSubstring(str, str1, str2))       
 
# This code is contributed by dharanendralv23

// C# program to implement
// the above approach
using System;
 
class GFG{
   
// Function to find the count of pairs of str1
// and str2 in str such that starting index of
// str1 less than or equal to str2 
static int CountSubstring(String str,
                          String str1,
                          String str2)
{
     
    // Stores count of pairs of str1 and str2
    // such that the start index of str1 is
    // less than or equal to str2
    int cntPairs = 0;
 
    // Stores count of substring str1 in
    // str whose start index is up to i
    int cntStr1 = 0;
 
    // Stores length of str
    int N = str.Length;
 
    // Stores length of str1
    int s1 = str1.Length;
 
    // Stores length of str2
    int s2 = str2.Length;
 
    // Iterate over the range [0, N -1]
    for(int i = 0; i < N; i++)
    {
         
        // If substring str1 whose
        // starting index is i
        if (((i + s1) <= N) &&
            (str.Substring(i, s1)).Equals(str1))
        {
             
            // Update cntStr1
            cntStr1++;
        }
 
        // If substring str2 whose
        // starting index is i
        else if (((i + s2) <= N) &&
                 (str.Substring(i, s2)).Equals(str2))
        {
             
            // Update cntPairs
            cntPairs += cntStr1;
        }
    }
    return cntPairs;
}
 
// Driver code
static public void Main()
{
    String str = "geeksforgeeksfor";        
    String str1 = "geeks";   
    String str2 = "for";
     
    Console.Write(CountSubstring(str, str1, str2));        
}
}
 
// This code is contributed by dharanendralv23

<script>
// JavaScript program to implement
// the above approach
 
// Function to find the count of pairs of str1
// and str2 in str such that starting index of
// str1 less than or equal to str2
function CountSubstring(str, str1, str2)
{
 
    // Stores count of pairs of str1 and str2
    // such that the start index of str1 is
    // less than or equal to str2
    var cntPairs = 0;
 
    // Stores count of substring str1 in
    // str whose start index is up to i
    var cntStr1 = 0;
 
    // Iterate over the range [0, N -1]
    for (let i = 0; i < str.length; i++) {
 
        // If substring str1 whose
        // start index is i
        if (str.substr(i, str1.length)
            == str1) {
 
            // Update cntStr1
            cntStr1++;
        }
 
        // If substring str2 whose
        // start index is i
        else if (str.substr(i, str2.length)
                 == str2) {
 
            // Update cntPairs
            cntPairs += cntStr1;
        }
    }
 
    return cntPairs;
}
 
// Driver Code
 
var str = "geeksforgeeksfor";
var str1 = "geeks", str2 = "for";
 
console.log( CountSubstring(str, str1, str2));
 
// This code is contributed by ukasp. 
</script>

3

Complejidad de tiempo: O(|str| * (|str1| + |str2|))  
Espacio auxiliar: O(1)