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: 4
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 : 2
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