2026-07-26T03:02:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11536 2024-03-06T10:48:15Z ddc:004 open_access

An Improved Data Structure for Left-Right Maximal Generic Words Problem Fujishige, Yuta Nakashima, Yuto Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki generic words suffix trees string processing algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuta Fujishige and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.40 urn:nbn:de:0030-drops-115366 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.40 eng https://creativecommons.org/licenses/by/3.0/legalcode