1 |
Dynamic Suffix Array with Polylogarithmic Queries and Updates ...
|
|
|
|
BASE
|
|
Show details
|
|
3 |
Breaking the $O(n)$-Barrier in the Construction of Compressed Suffix Arrays ...
|
|
|
|
BASE
|
|
Show details
|
|
5 |
Time-Space Tradeoffs for Finding a Long Common Substring ...
|
|
|
|
BASE
|
|
Show details
|
|
6 |
Time-Space Tradeoffs for Finding a Long Common Substring ...
|
|
|
|
BASE
|
|
Show details
|
|
7 |
Practical Performance of Space Efficient Data Structures for Longest Common Extensions ...
|
|
|
|
BASE
|
|
Show details
|
|
9 |
Longest Unbordered Factor in Quasilinear Time
|
|
Kociumaka, Tomasz; Kundu, Ritu; Mohamed, Manal. - : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. : LIPIcs - Leibniz International Proceedings in Informatics. 29th International Symposium on Algorithms and Computation (ISAAC 2018), 2018
|
|
BASE
|
|
Show details
|
|
13 |
Efficient Index for Weighted Sequences
|
|
Barton, Carl; Kociumaka, Tomasz; Pissis, Solon P.. - : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. : LIPIcs - Leibniz International Proceedings in Informatics. 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 2016
|
|
BASE
|
|
Show details
|
|
14 |
Minimal Suffix and Rotation of a Substring in Optimal Time
|
|
Kociumaka, Tomasz. - : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. : LIPIcs - Leibniz International Proceedings in Informatics. 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), 2016
|
|
BASE
|
|
Show details
|
|
15 |
Minimal Suffix and Rotation of a Substring in Optimal Time ...
|
|
Kociumaka, Tomasz. - : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany, 2016
|
|
Abstract:
For a text of length $n$ given in advance, the substring minimal suffix queries ask to determine the lexicographically minimal non-empty suffix of a substring specified by the location of its occurrence in the text. We develop a data structure answering such queries optimally: in constant time after linear-time preprocessing. This improves upon the results of Babenko et al. (CPM 2014), whose trade-off solution is characterized by Theta(n log n) product of these time complexities. Next, we extend our queries to support concatenations of O(1) substrings, for which the construction and query time is preserved. We apply these generalized queries to compute lexicographically minimal and maximal rotations of a given substring in constant time after linear-time preprocessing. Our data structures mainly rely on properties of Lyndon words and Lyndon factorizations. We combine them with further algorithmic and combinatorial tools, such as fusion trees and the notion of order isomorphism of strings. ...
|
|
Keyword:
Computer Science
|
|
URL: http://drops.dagstuhl.de/opus/volltexte/2016/6062/ https://dx.doi.org/10.4230/lipics.cpm.2016.28
|
|
BASE
|
|
Hide details
|
|
16 |
Sparse Suffix Tree Construction in Optimal Time and Space ...
|
|
|
|
BASE
|
|
Show details
|
|
17 |
Minimal Suffix and Rotation of a Substring in Optimal Time ...
|
|
|
|
BASE
|
|
Show details
|
|
|
|