文章基本信息

标题：Longest Common Extensions with Recompression
本地全文：下载
作者：Tomohiro I
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：78
页码：18:1-18:15
DOI：10.4230/LIPIcs.CPM.2017.18
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Given two positions i and j in a string T of length N, a longest common extension (LCE) query asks for the length of the longest common prefix between suffixes beginning at i and j. A compressed LCE data structure stores T in a compressed form while supporting fast LCE queries. In this article we show that the recompression technique is a powerful tool for compressed LCE data structures. We present a new compressed LCE data structure of size O(z lg (N/z)) that supports LCE queries in O(lg N) time, where z is the size of Lempel-Ziv 77 factorization without self-reference of T. Given T as an uncompressed form, we show how to build our data structure in O(N) time and space. Given T as a grammar compressed form, i.e., a straight-line program of size n generating T, we show how to build our data structure in O(n lg (N/n)) time and O(n + z lg (N/z)) space. Our algorithms are deterministic and always return correct answers.
关键词：Longest Common Extension (LCE) queries; compressed data structure; grammar compressed strings; Straight-Line Program (SLP)