Randomized efficient algorithms for compressed strings: The finger-print approach

Denote by LZ(w) the coded form of a string w produced by Lempel-Ziv encoding algorithm. We consider several classical algorithmic problems for texts in the compressed setting. The first of them is the equality-testing: given LZ(w) and integers i,j,k test the equality: w[i…i+ k] = w[j… j + k]. We give a simple and efficient randomized algorithm for this problem using the finger-printing idea. The equality testing is reduced to the equivalence of certain context-free grammars generating single strings. The equality-testing is the bottleneck in other algorithms for compressed texts. We relate the time complexity of several classical problems for texts to the complexity Eq(n) of equality-testing. Assume n = |LZ(T)|, m = |LZ(P)| and U = |T|. Then we can compute the compressed representations of the sets of occurrences of P in T, periods of T, palindromes of T, and squares of T respectively in times O(n log² U · Eq(m) + n² log U), O(n log² U · Eq(n) + n² log U), O(n log² U ·Eq(n) + n² log U) and O(n² log³ U · Eq(n) + n³ log² U), where Eq(n) = O(n log log n). The randomization improves considerably upon the known deterministic algorithms.