^{1} Department of Applied Mathematics and Computer Science, Technical University of Denmark^{2} Algorithms and Logic, Department of Applied Mathematics and Computer Science, Technical University of Denmark^{3} University of Warwick^{4} Department of Informatics and Mathematical Modeling, Technical University of Denmark

DOI:

10.1007/978-3-642-40104-6_13

Abstract:

The Karp-Rabin fingerprint of a string is a type of hash value that due to its strong properties has been used in many string algorithms. In this paper we show how to construct a data structure for a string S of size N compressed by a context-free grammar of size n that answers fingerprint queries. That is, given indices i and j, the answer to a query is the fingerprint of the substring S[i,j]. We present the first O(n) space data structures that answer fingerprint queries without decompressing any characters. For Straight Line Programs (SLP) we get O(logN) query time, and for Linear SLPs (an SLP derivative that captures LZ78 compression and its variations) we get O(loglogN) query time. Hence, our data structures has the same time and space complexity as for random access in SLPs. We utilize the fingerprint data structures to solve the longest common extension problem in query time O(logNlogℓ) and O(logℓloglogℓ + loglogN) for SLPs and Linear SLPs, respectively. Here, ℓ denotes the length of the LCE.

ISBN:

9783642401046, 9783642401039

Type:

Conference paper

Language:

English

Published in:

Lecture Notes in Computer Science: 13th International Symposium, Wads 2013, London, On, Canada, August 12-14, 2013. Proceedings, 2013, p. 146-157

Main Research Area:

Science/technology

Publication Status:

Published

Series:

Lecture Notes in Computer Science

Review type:

Peer Review

Conference:

Algorithms And Data Structures Symposium (WADS 2013)Algorithms and Data Structures Symposium