Tight lower bounds for the longest common extension problem
| Autor: | Dmitry Kosolobov |
|---|---|
| Přispěvatelé: | Department of Computer Science, Genome-scale Algorithmics research group / Veli Mäkinen |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
FOS: Computer and information sciences
Data structures Trade-off 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics Memory cell Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) Cell-probe model Mathematics Discrete mathematics String (computer science) Extension (predicate logic) Lower bounds Data structure 113 Computer and information sciences Computer Science Applications 010201 computation theory & mathematics Signal Processing Longest common extension 020201 artificial intelligence & image processing Alphabet Information Systems |
| Popis: | The longest common extension problem is to preprocess a given string of length $n$ into a data structure that uses $S(n)$ bits on top of the input and answers in $T(n)$ time the queries $\mathit{LCE}(i,j)$ computing the length of the longest string that occurs at both positions $i$ and $j$ in the input. We prove that the trade-off $S(n)T(n) = \Omega(n\log n)$ holds in the non-uniform cell-probe model provided that the input string is read-only, each letter occupies a separate memory cell, $S(n) = \Omega(n)$, and the size of the input alphabet is at least $2^{8\lceil S(n) / n\rceil}$. It is known that this trade-off is tight. Comment: 5 pages, accepted to Information Processing Letters |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|