Consultas para encontrar frecuencias de una string dentro de substrings especificadas

Dada una string S y una array Q de consultas, cada una especificando los índices inicial y final L( = Q[i][0]) y R( = Q[i][0]) respectivamente de una substring de S, la tarea es encontrar la frecuencia de la string K en la substring [L, R] .

Nota: Los rangos siguen la indexación basada en 1. 

Ejemplos: 

Entrada: S = “GFGFFGFG”, K = “GFG”, Q = {{1, 8}, {3, 5}, {5, 8}} 
Salida: 
2 
0 
1 
Explicación: Para la consulta 1, hay 2 ( “GFG”) substrings del índice 1 al índice 8. Una es del índice 1 al 3 y la otra es del índice 6 al 8. 
Para la consulta 2, hay 0 substrings (“GFG”) del índice 3 al 5. 
Para la consulta 3, hay 1 substring («GFG») del índice 5 al índice 8. La única substring es del índice 6 al 8.

Entrada: S = “ABCABCABABC”, K = “ABC”, Q = {{1, 6}, {5, 11}} 
Salida: 
2 
1 

Enfoque ingenuo: 
ejecute un ciclo de L a R para todas las consultas. Cuente la aparición de la string K y devuelva el recuento. 

Complejidad temporal: O(longitud de Q * |S|).

Enfoque eficiente: 
precalcule y almacene la frecuencia de K para cada índice. Ahora, para calcular la frecuencia de la string en un rango [L, R] , solo necesitamos calcular la diferencia entre la frecuencia de K en el índice (R-1) y (L-1) . 

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

// C++ Program to find
// frequency of a string K
// in a substring [L, R] in S
 
#include <bits/stdc++.h>
#define max_len 100005
using namespace std;
 
// Store the frequency of
// string for each index
int cnt[max_len];
 
// Compute and store frequencies
// for every index
void precompute(string s, string K)
{
 
    int n = s.size();
    for (int i = 0; i < n - 1; i++) {
        cnt[i + 1]
            = cnt[i]
              + (s.substr(i, K.size()) == K);
    }
}
 
// Driver Code
int main()
{
    string s = "ABCABCABABC";
    string K = "ABC";
    precompute(s, K);
 
    vector<pair<int, int> > Q
        = { { 1, 6 }, { 5, 11 } };
 
    for (auto it : Q) {
        cout << cnt[it.second - 1]
                    - cnt[it.first - 1]
             << endl;
    }
 
    return 0;
}

// Java program to find
// frequency of a string K
// in a substring [L, R] in S
class GFG{
     
static int max_len = 100005;
 
// Store the frequency of
// string for each index
static int cnt[] = new int[max_len];
 
// Compute and store frequencies
// for every index
public static void precompute(String s,
                              String K)
{
    int n = s.length();
     
    for(int i = 0; i < n - 2; i++)
    {
        cnt[i + 1] = cnt[i];
        if (s.substring(
            i, i + K.length()).equals(K))
        {
            cnt[i + 1] += 1;
        }
    }
    cnt[n - 2 + 1] = cnt[n - 2];
}
 
// Driver code
public static void main(String[] args)
{
    String s = "ABCABCABABC";
    String K = "ABC";
    precompute(s, K);
   
    int Q[][] = { { 1, 6 }, { 5, 11 } };
     
    for(int it = 0; it < Q.length; it++)
    {
        System.out.println(cnt[Q[it][1] - 1] -
                           cnt[Q[it][0] - 1]);
    }
}
}
 
// This code is contributed by divyesh072019

# Python3 Program to find
# frequency of a string K
# in a substring [L, R] in S
max_len = 100005
 
# Store the frequency of
# string for each index
cnt = [0] * max_len
 
# Compute and store frequencies
# for every index
def precompute(s, K):
 
    n = len(s)
    for i in range(n - 1):
        cnt[i + 1] = cnt[i]
        if s[i : len(K) + i] == K:
            cnt[i + 1] += 1
 
# Driver Code
if __name__ == "__main__":
 
    s = "ABCABCABABC"
    K = "ABC"
    precompute(s, K)
    Q = [[1, 6], [5, 11]]
 
    for it in Q:
        print(cnt[it[1] - 1] -
              cnt[it[0] - 1])
 
# This code is contributed by Chitranayal

// C# program to find frequency of
// a string K in a substring [L, R] in S
using System.IO;
using System;
 
class GFG{
     
static int max_len = 100005;
 
// Store the frequency of
// string for each index
static int[] cnt = new int[max_len];
 
// Compute and store frequencies
// for every index
static void precompute(string s,string K)
{
    int n = s.Length;
     
    for(int i = 0; i < n - 2; i++)
    {
        cnt[i + 1] = cnt[i];
         
        if (s.Substring(i, K.Length).Equals(K))
        {
            cnt[i + 1] += 1;
        }
    }
    cnt[n - 2 + 1] = cnt[n - 2];
}
 
// Driver code
static void Main()
{
    string s = "ABCABCABABC";
    string K = "ABC";
    precompute(s, K);
    int[,] Q = { { 1, 6 }, { 5, 11 } };
     
    for(int it = 0; it < Q.GetLength(0); it++)
    {  
        Console.WriteLine(cnt[Q[it, 1] - 1] -
                          cnt[Q[it, 0] - 1]);
    }
}
}
 
// This code is contributed by rag2127

<script>
 
// Javascript program to find
// frequency of a string K
// in a substring [L, R] in S
var max_len = 100005;
 
// Store the frequency of
// string for each index
var cnt = Array(max_len).fill(0);
 
// Compute and store frequencies
// for every index
function precompute(s, K)
{
    var n = s.length;
    for(var i = 0; i < n - 1; i++)
    {
        cnt[i + 1] = cnt[i] +
        (s.substring(i, i + K.length) == K);
    }
}
 
// Driver Code
var s = "ABCABCABABC";
var K = "ABC";
precompute(s, K);
var Q = [ [ 1, 6 ], [ 5, 11 ] ];
 
Q.forEach((it) => {
     
    document.write(cnt[it[1] - 1] -
                   cnt[it[0] - 1] + "<br>");
});
 
// This code is contributed by itsok
 
</script>

2
1

Complejidad de tiempo: O( | S | + longitud de Q ) , ya que cada consulta se responde en O(1). 
Espacio Auxiliar: O( |S| )