# Tag Info

13

A quick recap first. We are looking for a pattern $P[1\ldots m]$ in a string $S[1\ldots n]$. The Rabin-Karp algorithm does this by defining a hash function $h$. We compute $h(P)$ (that is, the hash of the pattern), and comparing it to $h(S[1\ldots m])$, $h(S[2\ldots m+1])$ and so on. If we find a matching hash, then it is a potential matching substring. The ...

11

Yes, in practice you can get by fine with just letting the computations overflow. You are effectively working modulo $2^{32}$. It also has the advantage of not requiring an (expensive) modulo computation. However, it lacks some of the theoretical performance guarantees. You need to be very careful with the choice of the base (in this case: $10$) with respect ...

4

Yes, you can solve your problem, roughly speaking, by precomputing prefix sums. In particular, if you are willing to do $O(n)$ precomputation and to use $O(n)$ space, we can solve your problem, for most standard rolling hashes. We just need the rolling hash to have one extra property, the inverse property. Most rolling hashes do have this property, ...

4

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, though this is not required. Then, for each $i$, search for all instances of $P_i$ in $T$ (with no mismatches), and see if it can extend to an instance of $P$...

3

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 value that is small (like 3), as that may make some computations faster.

3

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 hashing, 2-universal hashes, etc.). The Rabin fingerprint is also fine, and is essentially equivalent to the CRC (modulo small technical details that are ...

2

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 possible regardless of whether modular arithmetic is used or not. Going back to what you wrote though. Without the modular arithmetic, the division by R is possible ...

2

What you are missing is the identity $$(a + b) \bmod{Q} = (a \bmod{Q} + b \bmod{Q}) \bmod{Q}.$$

2

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 middle, adding other entries), you would need a little extra information to be able to insert into the middle at a latter access. As I see it , You need need to ...

2

In order to implement step 2, use a hash table. Add all the hashes of the $k$-length substrings of $s$ to the table. For each $k$-length substring of $t$, look it up on the table. This takes expected linear time for a large enough hash table.

2

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 functions that are good for this purpose. The trick is you calculate the hash of a small window of data bytes (say 64 bytes, but I've heard even as low as 16 works ...

2

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 the Rabin-fingerprint was designed to NOT be shift-resistant. In his paper (http://www.xmailserver.org/rabin.pdf) he used the fingerprint to detect any data-...

2

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 will definitely still work, although you can easily build a hash collision. With a=123456791 you may need more time to build a hash collision, but they still ...

1

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 may be that you missed some condtitions from the original question.

1

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 all substrings of S of length k. So, there are no decisions to make: every substring of length k gets hashed. Other systems may use the Rabin hash for other ...

1

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] \mod q$$ This is typically implemented as; h = 0 # Sometimes initialized to a seed value instead. for i in range(s): h = (p * h + S[i]) % q Note that this ...

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