Cuente distintas substrings de una string usando el algoritmo Rabin Karp

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.
 

#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

# 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=" ")

<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 ² ), N es la longitud de la string