Cuente el número de substrings distintas de una longitud dada

Dada una string S de longitud N que consta de alfabetos ingleses en minúsculas y un número entero ‘l’, encuentre el número de substrings distintas de longitud ‘l’ de la string dada. 

Ejemplos: 

Entrada: s = “abcbab”, l = 2 
Salida:
Todas las substrings distintas de longitud 2 
serán {“ab”, “bc”, “cb”, “ba”} 
Por lo tanto, la respuesta es igual a 4. 
Entrada: s = “ababa”, l = 2 
Salida :
 

Enfoque ingenuo: 
un enfoque simple será encontrar todas las substrings posibles, encontrar sus valores hash y encontrar el número de substrings distintas. 
Complejidad temporal: O(l*N)

Enfoque eficiente: 
Resolveremos este problema usando el algoritmo Rolling hash .

  • Encuentre el valor hash de la primera substring de longitud ‘l’. 
    Puede evaluarse como (s[0]-97)*x^(l-1) + (s[1]-97)*x^(l-2) … (s[l-1]-97). Llamemos a esto ‘H₁’.
  • Usando este valor hash, generaremos el siguiente hash como: 
    H 2 = (H 1 -(s[0]-97)*x^(l-1)*x + (s[l]-97). Generar hashes de todas las substrings de esta manera 
    y empujarlas en un conjunto desordenado.
  • Cuente el número de valores distintos en el conjunto.

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

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
#define x 26
#define mod 3001
using namespace std;
 
// Function to find the required count
int CntSubstr(string s, int l)
{
    // Variable to the hash
    int hash = 0;
 
    // Finding hash of substring
    // (0, l-1) using random number x
    for (int i = 0; i < l; i++) {
        hash = (hash * x + (s[i] - 97)) % mod;
    }
 
    // Computing x^(l-1)
    int pow_l = 1;
    for (int i = 0; i < l - 1; i++)
        pow_l = (pow_l * x) % mod;
 
    // Unordered set to add hash values
    unordered_set<int> result;
    result.insert(hash);
 
    // Generating all possible hash values
    for (int i = l; i < s.size(); i++) {
        hash = ((hash - pow_l * (s[i - l] - 97)
              + 2 * mod) * x + (s[i] - 97)) % mod;
        result.insert(hash);
    }
 
    // Print the result
    cout << result.size() << endl;
}
 
// Driver Code
int main()
{
    string s = "abcba";
 
    int l = 2;
 
    CntSubstr(s, l);
 
    return 0;
}

Java

// Java implementation of above approach
import java.util.*;
 
class GFG
{
 
    static int x = 26;
    static int mod = 3001;
 
    // Function to find the required count
    static void CntSubstr(char[] s, int l)
    {
        // Variable to the hash
        int hash = 0;
 
        // Finding hash of substring
        // (0, l-1) using random number x
        for (int i = 0; i < l; i++)
        {
            hash = (hash * x + (s[i] - 97)) % mod;
        }
 
        // Computing x^(l-1)
        int pow_l = 1;
        for (int i = 0; i < l - 1; i++)
        {
            pow_l = (pow_l * x) % mod;
        }
 
        // Unordered set to add hash values
        HashSet<Integer> result = new HashSet<Integer>();
        result.add(hash);
 
        // Generating all possible hash values
        for (int i = l; i < s.length; i++)
        {
            hash = ((hash - pow_l * (s[i - l] - 97)
                    + 2 * mod) * x + (s[i] - 97)) % mod;
            result.add(hash);
        }
 
        // Print the result
        System.out.println(result.size());
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        String s = "abcba";
 
        int l = 2;
 
        CntSubstr(s.toCharArray(), l);
    }
}
 
// This code contributed by Rajput-Ji

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
    static int x = 26;
    static int mod = 3001;
 
    // Function to find the required count
    static void CntSubstr(char[] s, int l)
    {
        // Variable to the hash
        int hash = 0;
 
        // Finding hash of substring
        // (0, l-1) using random number x
        for (int i = 0; i < l; i++)
        {
            hash = (hash * x + (s[i] - 97)) % mod;
        }
 
        // Computing x^(l-1)
        int pow_l = 1;
        for (int i = 0; i < l - 1; i++)
        {
            pow_l = (pow_l * x) % mod;
        }
 
        // Unordered set to add hash values
        HashSet<int> result = new HashSet<int>();
        result.Add(hash);
 
        // Generating all possible hash values
        for (int i = l; i < s.Length; i++)
        {
            hash = ((hash - pow_l * (s[i - l] - 97)
                    + 2 * mod) * x + (s[i] - 97)) % mod;
            result.Add(hash);
        }
 
        // Print the result
        Console.WriteLine(result.Count);
    }
 
    // Driver Code
    public static void Main(String[] args)
    {
        String s = "abcba";
 
        int l = 2;
 
        CntSubstr(s.ToCharArray(), l);
    }
}
 
/* This code contributed by PrinciRaj1992 */

Python3

# Python3 implementation of above approach
x = 26
mod = 3001
 
# Function to find the required count
def CntSubstr(s, l) :
 
    # Variable to the hash
    hash = 0;
 
    # Finding hash of substring
    # (0, l-1) using random number x
    for i in range(l) :
        hash = (hash * x + (ord(s[i]) - 97)) % mod;
 
    # Computing x^(l-1)
    pow_l = 1;
    for i in range(l-1) :
        pow_l = (pow_l * x) % mod;
 
    # Unordered set to add hash values
    result = set();
    result.add(hash);
 
    # Generating all possible hash values
    for i in range(l,len(s)) :
        hash = ((hash - pow_l * (ord(s[i - l]) - 97)
            + 2 * mod) * x + (ord(s[i]) - 97)) % mod;
         
        result.add(hash);
 
    # Print the result
    print(len(result)) ;
 
 
# Driver Code
if __name__ == "__main__" :
 
    s = "abcba";
 
    l = 2;
 
    CntSubstr(s, l);
     
# This code is contributed by AnkitRai01

Javascript

<script>
 
// Javascript implementation of above approach
var x = 26;
var mod = 3001;
 
// Function to find the required count
function CntSubstr(s, l)
{
    // Variable to the hash
    var hash = 0;
 
    // Finding hash of substring
    // (0, l-1) using random number x
    for (var i = 0; i < l; i++) {
        hash = (hash * x + (s[i].charCodeAt(0) - 97)) % mod;
    }
 
    // Computing x^(l-1)
    var pow_l = 1;
    for (var i = 0; i < l - 1; i++)
        pow_l = (pow_l * x) % mod;
 
    // Unordered set to add hash values
    var result = new Set();
    result.add(hash);
 
    // Generating all possible hash values
    for (var i = l; i < s.length; i++) {
        hash = ((hash - pow_l * (s[i - l].charCodeAt(0) - 97)
              + 2 * mod) * x + (s[i].charCodeAt(0) - 97)) % mod;
        result.add(hash);
    }
 
    // Print the result
    document.write( result.size );
}
 
// Driver Code
var s = "abcba";
var l = 2;
CntSubstr(s, l);
 
</script>
Producción: 

4

 

Complejidad de tiempo : O(N)

Espacio Auxiliar: O(|s|)
 

Publicación traducida automáticamente

Artículo escrito por DivyanshuShekhar1 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 *