Compact data structures for shortest unique substring queries

DOI10.1007/978-3-030-32686-9_8MaRDI QIDQ6536247zbMATH OpenFDO

Authors Takuya Mieno, Dominik Köppl, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Publication date 19 April 2024

zbMATH Keywords

compact data structureshortest unique substringstring processing algorithm

Mathematics Subject Classification ID

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

Recommendations

• Space-efficient algorithms for computing minimal/shortest unique substrings
• Tight bounds on the maximum number of shortest unique substrings
• Shortest unique substring query revisited
• Shortest Unique Substring Queries on Run-Length Encoded Strings
• A simple yet time-optimal and linear-space algorithm for shortest unique substring queries

Cites work

• scientific article; zbMATH DE number 2230164 (Why is no real title available?)
• A simple yet time-optimal and linear-space algorithm for shortest unique substring queries
• Shortest Unique Substring Queries on Run-Length Encoded Strings
• Shortest unique substrings queries in optimal time
• Space-time trade-offs for finding shortest unique substrings and maximal unique matches
• Succinct representations of binary trees for range minimum queries
• Suffix Arrays: A New Method for On-Line String Searches

Cited in

(2)

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

This page was built for publication: Compact data structures for shortest unique substring queries

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