2
$\begingroup$

Context: I've been working through Cracking the Code Interview and on page 70 the book asserts that there is a O(B) solution to this problem.

If

  • s = little string and S = len(s)
  • b = big string and B = len(b)

then I believe it would be something along the lines of (pseudocode):

hs = hash(s)
for every position, substring of length S in B: 
    h_sub = hash(substring)
    if hs == h_sub:
         print position

Note that the for loop will run B-S+1 times, so whatever happens inside the loop must be O(1) in order for the whole thing to be O(B).

This assumes that there exists a O(1) hash function hash(s) that only returns the same hash when two words are permutations of each other, and never collide otherwise.

What is this hash function? It seems like you'd have to iterate through every letter in substring to calculate h_sub and I don't see how that can happen in less than O(S) time. This answer seemed promising but then someone found a non-valid collision.

I learned about the radix-2p hash for this problem in school and we had to prove it as a homework exercise so I am convinced of its correctness.

However in the calculation $k = \sum_{i=0}^{n-1} x_i(2^{p})^i$, the exponent on the $2^p$ always changes depending on the position of the letter $x_i$ within the substring, so I don't see how we can avoid having to iterate anew through all S letters of the substring when we calculate $k \text{ mod } (2^p-1)$.

Am I missing something or is there another approach entirely? Thanks.

$\endgroup$
2
$\begingroup$

I think a hash is the wrong approach. Instead you can use auxiliary variables: an array $A$ and an integer $c$. Basically $A$ tracks the error in the number of occurrences of each character and $c$ tracks the number of non-zero errors. Instead of a hash update you update the count of the character which drops out, then update $c$ if it changed from or to zero, then repeat for the character which is coming in. After that, if $c=0$ you found a permutation of $s$.

$\endgroup$
1
$\begingroup$

One simple hash is

$$\text{hash}(s) = s[0] + s[1] + \dots + s[n-1] \bmod p,$$

where $s[0],\dots,s[n-1]$ are the characters of the string $s$. You could also replace addition modulo $p$ with xor, or any other commutative operation. You also need the hash to be a rolling hash so that you can compute $\text{hash}(B[i+1..i+k])$ from $\text{hash}(B[i..i+k-1])$ efficiently, but fortunately the above hash functions have that property.

The worst-case running time could be $O(|s| \cdot |B|)$ (because in principle you could have a hash collision in every position), but in practice it will often run in time $O(|B|)$ if the strings $s,B$ aren't "too unfriendly".

If you want stronger guarantees, or just want to heuristically reduce hash collisions, here is a better hash:

$$\text{hash}(s) = \sum_{i=0}^{n-1} T[s[i]] \bmod p,$$

where $T[\cdot]$ is a lookup table with one entry per possible character value. (For example, if every character is a 8-bit byte, then $T$ is a lookup table with 256 entries.) This hash will have fewer collisions, and still has all the properties needed -- it is commutative and a rolling hash. If you fill in the entries of $T$ randomly, one can prove stronger guarantees: the expected running time will be $O(|B|)$, and the running time will be at most $c \cdot |B|$ with probability exponentially small in $c$ (so in practice the running time can be upper-bounded by something like $100 \cdot |B|$ for all intents and purposes). This is a consequence of the fact that $\Pr[\text{hash}(s) = \text{hash}(t)] \le 1/p$ for all $s \ne t$, when $T$ is initialized in this way.

$\endgroup$
  • 1
    $\begingroup$ Ah I see! Thanks. If I understand correctly, the idea is that I use a rolling hash, but only when there is a collision do I check every letter of s against every letter of substring. And collisions should be uncommon enough that runtime will average out to O(B) in practice. This satisfies me for all practical purposes :) But does this mean there is no "true" O(B) algorithm in a strict sense? $\endgroup$ – SlugFrisco Mar 13 at 19:55
  • $\begingroup$ @SlugFrisco, yup, exactly! I've edited my answer to describe a hash function where we can prove a stronger fact about the running time; in some rigorous sense it can reasonably be considered $O(|B|)$. $\endgroup$ – D.W. Mar 13 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.