Range shortest unique substring queries

DOI10.1007/978-3-030-32686-9_18MaRDI QIDQ6536259zbMATH OpenFDO

Authors Paniz Abedin, Arnab Ganguly, Solon P. Pissis, Sharma V. Thankachan

Publication date 19 April 2024

zbMATH Keywords

geometric data structuressuffix treerange queriesshortest unique substringheavy-light decomposition

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• Compact data structures for shortest unique substring queries
• Space-efficient algorithms for computing minimal/shortest unique substrings
• Shortest Unique Substring Queries on Run-Length Encoded Strings
• Shortest unique substring query revisited
• Shortest unique substrings queries in optimal time

Cites work

• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• A linear space data structure for range LCP queries
• A linear-space data structure for range-LCP queries in poly-logarithmic time
• Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis
• Algorithms and combinatorial properties on shortest unique palindromic substrings
• Fast Algorithms for Finding Nearest Common Ancestors
• Maximal motif discovery in a sliding window
• Orthogonal point location and rectangle stabbing queries in 3-d
• Range LCP
• Recursive Star-Tree Parallel Data Structure
• Shortest Unique Substring Queries on Run-Length Encoded Strings
• Shortest unique palindromic substring queries on run-length encoded strings
• Shortest unique substring query revisited
• Shortest unique substrings queries in optimal time
• Space-time trade-offs for finding shortest unique substrings and maximal unique matches
• Space-time trade-offs for the shortest unique substring problem

Cited in

(1)

• Internal shortest absent word queries in constant time and linear space

This page was built for publication: Range shortest unique substring queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6536259)