Deterministic Sparse Suffix Sorting in the Restore Model
| Autor: | Tomohiro I, Johannes Fischer, Dominik Köppl |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
LCP array Suffix array 0102 computer and information sciences 02 engineering and technology Space (mathematics) 01 natural sciences 020202 computer hardware & architecture law.invention Combinatorics Suffix sorting Mathematics (miscellaneous) 010201 computation theory & mathematics law Computer Science - Data Structures and Algorithms Data_FILES 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) Online algorithm Mathematics |
| Zdroj: | ACM Transactions on Algorithms. 16:1-53 |
| ISSN: | 1549-6333 1549-6325 |
| DOI: | 10.1145/3398681 |
| Popis: | Given a text T of length n , we propose a deterministic online algorithm computing the sparse suffix array and the sparse longest common prefix array of T in O( c √ lg n + m lg m lg n lg * n ) time with O( m ) words of space under the premise that the space of T is rewritable, where m ≤ n is the number of suffixes to be sorted (provided online and arbitrarily), and c is the number of characters with m ≤ c ≤ n that must be compared for distinguishing the designated suffixes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|