de Cipher idea de "base primordial" debería funcionar bastante bien - aunque la solución que publicó parece un poco rara.
no creo que haya ninguna necesidad de multiplicación inversa en este método. Aquí está mi solución:
Digamos que la cadena que tenemos hash es "abc", y queremos agregar "d" y quitar "a".
Al igual que Cipher, mi algoritmo de hash básica será:
unsigned hash(const string& s)
{
unsigned ret = 0;
for (int i = 0; i < s.size(); i++)
{
ret *= PRIME_BASE; //shift over by one
ret += s[i]; //add the current char
ret %= PRIME_MOD; //don't overflow
}
return ret;
}
Ahora, para implementar deslizamiento:
hash1 = [0]*base^(n-1) + [1]*base^(n-2) + ... + [n-1]
Nos gustaría añadir algo al final y quite el primer valor , por lo
hash2 = [1]*base^(n-1) + [2]*base^(n-2) + ... + [n]
En primer lugar podemos añadir la última letra:
hash2 = (hash1 * PRIME_BASE) + newchar;
=> [0]*base^n + [1]*base^(n-1) + ... + [n-1]*base + [n]
Luego sólo hay que restar el primer carácter:
hash2 -= firstchar * pow(base, n);
=> [1]*base^(n-1) + ... + [n]
Una nota importante: hay que tener cuidado con desbordamiento. Usted puede optar por dejar que se desborde unsigned int, pero creo que es mucho más propenso a la colisión
Aquí está mi aplicación (pero también más rápido!):
#include <iostream>
#include <string>
using namespace std;
const unsigned PRIME_BASE = 257;
const unsigned PRIME_MOD = 1000000007;
unsigned hash(const string& s)
{
long long ret = 0;
for (int i = 0; i < s.size(); i++)
{
ret = ret*PRIME_BASE + s[i];
ret %= PRIME_MOD; //don't overflow
}
return ret;
}
int rabin_karp(const string& needle, const string& haystack)
{
//I'm using long longs to avoid overflow
long long hash1 = hash(needle);
long long hash2 = 0;
//you could use exponentiation by squaring for extra speed
long long power = 1;
for (int i = 0; i < needle.size(); i++)
power = (power * PRIME_BASE) % PRIME_MOD;
for (int i = 0; i < haystack.size(); i++)
{
//add the last letter
hash2 = hash2*PRIME_BASE + haystack[i];
hash2 %= PRIME_MOD;
//remove the first character, if needed
if (i >= needle.size())
{
hash2 -= power * haystack[i-needle.size()] % PRIME_MOD;
if (hash2 < 0) //negative can be made positive with mod
hash2 += PRIME_MOD;
}
//match?
if (i >= needle.size()-1 && hash1 == hash2)
return i - (needle.size()-1);
}
return -1;
}
int main()
{
cout << rabin_karp("waldo", "willy werther warhol wendy --> waldo <--") << endl;
}
Para cualquiera que haya llegado aquí buscando hash rolling y multiplicación inversa. Solo necesita dividir (o usar el inverso multiplicativo) si su implementación de hash rodante necesita soportar longitud variable y probablemente no lo necesite si quiere hacer Rabin-Karp. Algunos consejos sobre cómo usar la inversa en este [video] (https://www.youtube.com/watch?v=w6nuXg0BISo) y mi intento de implementación en [python] (https://pastebin.com/BGuxv1cM). – Cedric