What's the deal with Deno? We talk with a major contributor to find out. Listen now.

# Questions tagged [rolling-hash]

The tag has no usage guidance.

14 questions
Filter by
Sorted by
Tagged with
48 views

### Rolling hash hacking

The hash value of a string $s$ is given by $$h(s) = \sum^{|s|}_{i = 1} s_i \cdot p^{|s| - i} \mod m; \text{ m is prime, m < 10^{12}}.$$ The string $s$, $p$, $m$ is given, $|s| \le 14$, ...
51 views

### finding all cyclic substrings of a string

I have been stuck on this problem for a while now; any help would be appreciated. Given a string S, find the number of distinct substrings which are composed of 2 or more consecutive strings. For ...
872 views

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

In the Rabin Karp algorithm the rolling hash is calculated as follows: H1= c1*a^k-1 + c2*a^k-2+c3*a^k-3+…+ck*a^0 where a is a ...
2k views

### Rolling Hash calculation with Horner's method

I understood how Horner's method reduces the complexity(number of operations) while evaluating a polynomial. I have a character array derived from a string ...
2k views

### How does Rabin fingerprint finds breakpoints (chunk boundary)?

I was reading up on chunking and found Rabin fingerprinting is also used to break files into chunks. After reading about this algorithm, I understood how rolling hash is computed using Rabin ...
677 views

### modular arithmetic in rolling hash algorithm

My question was around the rolling hash function in RobinKarp algorithm. It is intuitive for me to understand how to get from xi to xi+1 without the mod, however with the mod i am not sure how we ...
117 views

### Adding a character in the middle (rolling hash)

Is there a way to support adding characters in the middle and update the hash in O(1) ? All I have is the hash of ABBDE and I want to get the hash of ABBCDE.
48 views

### Repeated fingerprinting after array updates

I've got a microprocessor and want to quickly identify the settings of my application (stored in some eeprom regions) via a fingerprint instead of having to dump the entire memory every time. So I ...
638 views

### pattern search with k-mismatch

I have used Rabin Karp Rolling Hash for searching a pattern $P$ in a text $T$. Now I am allowing $k$-mismatches, but not able to do a faster implementation. I tried modifying RK algorithm by ...
898 views

### Does the Rabin-Karp really need me to care about applying a mod Q operation on the rolling hashes?

I have been reading about the Rabin Karp algorithm and I kept wondering what's the big deal with keeping our rolling hashes values bounded by a value Q? I'd thought that as our integer number ...
2k views

### Finding hash of a substring $[i, j]$ in $O(1)$ using $O(|S|)$ pre computation

Given a string $S$ of length $n$ characters, is it possible to calculate the hash of its substring $[i, j]$ (from index $i$ to $j$, both inclusive) in $O(1)$ using some form of precomputation? Can we ...
3k views

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

The Rabin–Karp string matching algorithm requires a hash function which can be computed quickly. A common choice is $$h(x_0\ldots x_n) = \sum_{i=0}^n b^i x_i,$$ where $b$ is prime (all computations ...
The longest common substring (LCS) of two input strings $s,t$ is a common substring (in both of them) of maximum length. We can relax the constraints to generalize the problem: find a common substring ...