A linear-space data structure for range-LCP queries in poly-logarithmic time

DOI10.1016/j.tcs.2020.04.009zbMath1455.68045OpenAlexW3017834538MaRDI QIDQ5918832

Wing-Kai Hon, Rahul Shah, Arnab Ganguly, Kunihiko Sadakane, Kotaro Matsuda, Yakov Nekrich, Sharma V. Thankachan, Paniz Abedin

Publication date: 23 May 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.04.009

zbMATH Keywords

string algorithmslongest common prefixindexing version

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Algorithms on strings (68W32)

Related Items (2)

Internal shortest absent word queries in constant time and linear space ⋮ Finding top-\(k\) longest palindromes in substrings

Cites Work

• Unnamed Item
• String processing and information retrieval. 22nd international symposium, SPIRE 2015, London, UK, September 1--4, 2015. Proceedings
• A data structure for dynamic trees
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Generalized substring compression
• Orthogonal Range Searching for Text Indexing
• Faster Range LCP Queries
• Sorted Range Reporting
• Weighted Ancestors in Suffix Trees
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Fast Algorithms for Finding Nearest Common Ancestors
• A Linear Space Data Structure for Range LCP Queries*
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Document Listing on Repetitive Collections
• Orthogonal range searching on the RAM, revisited
• Range LCP
• A linear-space data structure for range-LCP queries in poly-logarithmic time
• Range LCP

This page was built for publication: A linear-space data structure for range-LCP queries in poly-logarithmic time