Good Primes
Background: The Karp-Rabin fingerprint fp(s) of a binary string s[1..k] = sum_{i=1}^{k} s[i] 2^{k-i} mod p, where p is a prime. Fingerprints are good for comparing strings.
Given a binary string t[1..n] and a prime p, p is said to be good for t if for all i, j and k, we have t[i,i+k]=t[j,j+k] iff fp(t[i,i+k])=fp(t[j,j+k]). Our problem is to verify if p is good for t. It is trivial to verify this in O(n^2) time, but the goal is to (a) design a faster--linear time--deterministic algorithm, or (b) sublinear time randomized algorithm which is approximately correct, a la property testing algorithms.
[Btw, Karp-Rabin analysis shows that there are so many good primes in the range polynomial in n that choosing a random prime will be good with high probability. This is the property a lot of string matching algorithms use.]
Given a binary string t[1..n] and a prime p, p is said to be good for t if for all i, j and k, we have t[i,i+k]=t[j,j+k] iff fp(t[i,i+k])=fp(t[j,j+k]). Our problem is to verify if p is good for t. It is trivial to verify this in O(n^2) time, but the goal is to (a) design a faster--linear time--deterministic algorithm, or (b) sublinear time randomized algorithm which is approximately correct, a la property testing algorithms.
[Btw, Karp-Rabin analysis shows that there are so many good primes in the range polynomial in n that choosing a random prime will be good with high probability. This is the property a lot of string matching algorithms use.]
posted by metoo at 9:49 AM
0 Comments:
Post a Comment
<< Home