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>
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