Dada una string, cuente el número de substrings distintas utilizando el algoritmo Rabin Karp.
Ejemplos :
Input : str = “aba” Output : 5 Explanation : Total number of distinct substring are 5 - "a", "ab", "aba", "b" ,"ba" Input : str = “abcd” Output : 10 Explanation : Total number of distinct substring are 10 - "a", "ab", "abc", "abcd", "b", "bc", "bcd", "c", "cd", "d"
Acercarse:
Requisito previo : Algoritmo de Rabin-Karp para la búsqueda de patrones
Calcule el valor hash actual del carácter actual y guárdelo
en un diccionario/mapa para evitar repeticiones.
Para calcular el hash (hash rodante) como se hace en el algoritmo de Rabin-Karp, sigue:
La función hash sugerida por Rabin y Karp calcula un valor entero. El valor entero de una string es el valor numérico de una string. Por ejemplo, si todos los caracteres posibles son del 1 al 10, el valor numérico de «122» será 122. El número de caracteres posibles es superior a 10 (256 en general) y la longitud del patrón puede ser grande. Por lo tanto, los valores numéricos no se pueden almacenar prácticamente como un número entero. Por lo tanto, el valor numérico se calcula utilizando aritmética modular para garantizar que los valores hash se puedan almacenar en una variable entera (que quepa en palabras de memoria). Para hacer un refrito, debemos quitar el dígito más significativo y agregar el nuevo dígito menos significativo para el valor hash. El refrito se realiza utilizando la siguiente fórmula.
hash( txt[s+1 .. s+m] ) = ( d ( hash( txt[s .. s+m-1]) – txt[s]*h ) + txt[s + m] ) mod q
hash( txt[s .. s+m-1] ) : Valor hash en el turno s .
hash( txt[s+1 .. s+m] ) : Valor hash en el siguiente turno (o turno s +1)
d : Número de caracteres en el alfabeto
q : Un número primo
h: d^(m-1)
La idea es similar cuando evaluamos una expresión matemática. Por ejemplo, tenemos una string de «1234». Calculamos que el valor de la substring «12» es 12 y queremos calcular el valor de la substring «123». Esto se puede calcular como ((12)*10+3 )=123, aquí se aplica una lógica similar.
C++
#include <bits/stdc++.h> using namespace std; // Driver code int main() { int t = 1; // store prime to reduce overflow long long mod = 9007199254740881; for(int i = 0; i < t; i++) { // string to check number of distinct substring string s = "abcd"; // to store substrings vector<vector<long long>>l; // to store hash values by Rabin Karp algorithm unordered_map<long long,int>d; for(int i=0;i<s.length();i++){ int suma = 0; long long pre = 0; // Number of input alphabets long long D = 256; for(int j=i;j<s.length();j++){ // calculate new hash value by adding next element pre = (pre*D+s[j]) % mod; // store string length if non repeat if(d.find(pre) == d.end()) l.push_back({i, j}); d[pre] = 1; } } // resulting length cout<<l.size()<<endl; // resulting distinct substrings for(int i = 0; i < l.size(); i++) cout << s.substr(l[i][0],l[i][1]+1-l[i][0]) << " "; } } // This code is contributed by shinjanpatra
Python3
# importing libraries import sys import math as mt t = 1 # store prime to reduce overflow mod = 9007199254740881 for ___ in range(t): # string to check number of distinct substring s = 'abcd' # to store substrings l = [] # to store hash values by Rabin Karp algorithm d = {} for i in range(len(s)): suma = 0 pre = 0 # Number of input alphabets D = 256 for j in range(i, len(s)): # calculate new hash value by adding next element pre = (pre*D+ord(s[j])) % mod # store string length if non repeat if d.get(pre, -1) == -1: l.append([i, j]) d[pre] = 1 # resulting length print(len(l)) # resulting distinct substrings for i in range(len(l)): print(s[l[i][0]:l[i][1]+1], end=" ")
Javascript
<script> let t = 1 // store prime to reduce overflow let mod = 9007199254740881 for(let i = 0; i < t; i++){ // string to check number of distinct substring let s = 'abcd' // to store substrings let l = [] // to store hash values by Rabin Karp algorithm let d = new Map() for(let i=0;i<s.length;i++){ let suma = 0 let pre = 0 // Number of input alphabets let D = 256 for(let j=i;j<s.length;j++){ // calculate new hash value by adding next element pre = (pre*D+s.charCodeAt(j)) % mod // store string length if non repeat if(d.has([pre, -1]) == false) l.push([i, j]) d.set(pre , 1) } } // resulting length document.write(l.length,"</br>") // resulting distinct substrings for(let i = 0; i < l.length; i++) document.write(s.substring(l[i][0],l[i][1]+1)," ") } // This code is contributed by shinjanpatra </script>
10 a ab abc abcd b bc bcd c cd d
Complejidad del tiempo: O(N 2 ), N es la longitud de la string
Publicación traducida automáticamente
Artículo escrito por kfardeen7890 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA