# Randomized Efficient Algorithms for Compressed Strings: the Finger-Print Approach

Title | Randomized Efficient Algorithms for Compressed Strings: the Finger-Print Approach |

Publication Type | Technical Report |

Year of Publication | 1996 |

Authors | Gasieniec, L., Karpinski M., Plandowski W., & Rytter W. |

Other Numbers | 1031 |

Abstract | 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^2 U * Eq(m) + n^2 log U), O(n log^2 U * Eq(n) + n^2 log U), O(n log^2 U * Eq(n) + n^2 log U) and O(n^2 log^3 U * Eq(n) + n^3 log^2 U), where Eq(n) = O(n log log n). The randomization improves considerably upon the known deterministic algorithms. |

URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1996/tr-96-021.pdf |

Bibliographic Notes | ICSI Technical Report TR-96-021 |

Abbreviated Authors | L. Gasieniec, M. Karpinski, W. Plandowski, and W. Rytter |

ICSI Publication Type | Technical Report |