5 votes
Accepted

Understanding Rabin-Karp's rolling hash computation

Two modulo operations There are two modulo operations for a modulus $0\not=q\in\Bbb N$. $\newcommand{\q}{\!\!\pmod q}$ $\newcommand{\Q}{\text{mod}_q}$. Let $\text{mod}_q:\Bbb Z\to\Bbb Z/q\Bbb Z$, $\...
John L.'s user avatar
  • 38.8k
4 votes

pattern search with k-mismatch

Split into segments One simple approach is to split $P$ into $k+1$ pieces, say $P = P_0 P_1 \cdots P_k$, as @j_random_hacker suggests. You can make each of the $P_i$ be of approximately equal length,...
D.W.'s user avatar
  • 158k
4 votes

Why is the base used to compute hashes in Rabin–Karp always primes?

Pseudonym's answer is excellent, but there's some additional points worth mentioning. The generalized version of the hash algorithm used in the RabinKarp document is; $$h(S[0…s])=\sum_{i=0}^{s}p^iS[i] ...
Donovan Baarda's user avatar
4 votes
Accepted

By what criteria is the base value selected in Rabin Karp algorithm?

hash values, by definition, may collide this hash is computed (implicitly) by modulo of 2^N if you use N-bit integers recommended value of "a" is any large prime number, f.e. 123456791 With a=10, it ...
Bulat's user avatar
  • 1,853
4 votes

By what criteria is the base value selected in Rabin Karp algorithm?

You can use any value you want, but it is best to choose a value that is relatively prime to the modulus, as that reduces the number of hash collisions. For efficiency you might want to choose a ...
D.W.'s user avatar
  • 158k
3 votes

Repeated fingerprinting after array updates

Any of the first three options you list are likely to be fine for what you want. The CRC provides a good fingerprint (indeed, there's some theory to back that up, based on the theory of Carter-Wegman ...
D.W.'s user avatar
  • 158k
3 votes

How does Rabin fingerprint finds breakpoints (chunk boundary)?

Note that any hash algorithm can be used to break files into chunks where chunk boundaries don't change much after inserts/deletes. Rabin fingerprinting (and RabinKarp rollsums) are just hash ...
Donovan Baarda's user avatar
2 votes

modular arithmetic in rolling hash algorithm

The video actually does it the other way around, kicking out the term with the highest power and then multiplying by R. It turns out to not really make a difference, but this is clearly always ...
harold's user avatar
  • 2,028
2 votes
Accepted

modular arithmetic in rolling hash algorithm

What you are missing is the identity $$ (a + b) \bmod{Q} = (a \bmod{Q} + b \bmod{Q}) \bmod{Q}. $$
Yuval Filmus's user avatar
2 votes

Adding a character in the middle (rolling hash)

With just the Rolling HASH for the whole ABBDE, you can not insert into the middle of it. But... as I understand rolling Hash... If you are building the hashes up as you go (adding into the ...
Phillip Williams's user avatar
2 votes

How does Rabin fingerprint finds breakpoints (chunk boundary)?

I know I'm very late to this question, but I want to try and provide an answer for anyone who stumbles across this as I have. I went and deciphered the original paper by Michael Rabin, and found that ...
Owen Randall's user avatar
1 vote

How to use a worst case scenario in Rolling Hash: Rabin Karp Algorithm when the given string only contains the occurrences of "a and b?"

You can build a quick intuition by considering digit-only string and using the decimal value of the substring as its hash. Let's find substring "345" in string "123456789". At the ...
Bulat's user avatar
  • 1,853
1 vote
Accepted

How to use a worst case scenario in Rolling Hash: Rabin Karp Algorithm when the given string only contains the occurrences of "a and b?"

A clearer explanation Let $\beta$ be a positive integer. ($b$ will be used as a character) Let string $s=c_1c_2\cdots c_m$. Then $$H(s) = c_1\times \beta^{m-1} + c_2\times \beta^{m-2} + c_3\times \...
John L.'s user avatar
  • 38.8k
1 vote

Rolling hash hacking

Running birthday attack should be faster than writing the question: sqrt(1e12) = 1e6 Also note that your question have nothing with rolling hashes, moreover, with rolling hash len(s) is fixed. So it ...
Bulat's user avatar
  • 1,853
1 vote

How does Rabin fingerprint finds breakpoints (chunk boundary)?

It depends on what you are using the Rabin rolling hash for. If you want to check whether a string P of length k is contained in a large string S, then the Rabin algorithm computes the Rabin hash of ...
D.W.'s user avatar
  • 158k

Only top scored, non community-wiki answers of a minimum length are eligible