License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.40
URN: urn:nbn:de:0030-drops-115366
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11536/
Fujishige, Yuta ;
Nakashima, Yuto ;
Inenaga, Shunsuke ;
Bannai, Hideo ;
Takeda, Masayuki
An Improved Data Structure for Left-Right Maximal Generic Words Problem
Abstract
For a set D of documents and a positive integer d, a string w is said to be d-left-right maximal, if (1) w occurs in at least d documents in D, and (2) any proper superstring of w occurs in less than d documents. The left-right-maximal generic words problem is, given a set D of documents, to preprocess D so that for any string p and for any positive integer d, all the superstrings of p that are d-left-right maximal can be answered quickly. In this paper, we present an O(n log m) space data structure (in words) which answers queries in O(|p| + o log log m) time, where n is the total length of documents in D, m is the number of documents in D and o is the number of outputs. Our solution improves the previous one by Nishimoto et al. (PSC 2015), which uses an O(n log n) space data structure answering queries in O(|p|+ r * log n + o * log^2 n) time, where r is the number of right-extensions q of p occurring in at least d documents such that any proper right extension of q occurs in less than d documents.
BibTeX - Entry
@InProceedings{fujishige_et_al:LIPIcs:2019:11536,
author = {Yuta Fujishige and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda},
title = {{An Improved Data Structure for Left-Right Maximal Generic Words Problem}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {40:1--40:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-130-6},
ISSN = {1868-8969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11536},
URN = {urn:nbn:de:0030-drops-115366},
doi = {10.4230/LIPIcs.ISAAC.2019.40},
annote = {Keywords: generic words, suffix trees, string processing algorithms}
}
Keywords: |
|
generic words, suffix trees, string processing algorithms |
Collection: |
|
30th International Symposium on Algorithms and Computation (ISAAC 2019) |
Issue Date: |
|
2019 |
Date of publication: |
|
28.11.2019 |