Compact data structures for shortest unique substring queries

DOI10.1007/978-3-030-32686-9_8zbMATH Open1539.68089MaRDI QIDQ6536247FDOQ6536247

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

Publication date: 19 April 2024

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

zbMATH Keywords

compact data structureshortest unique substringstring processing algorithm

Mathematics Subject Classification ID

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

Cites Work

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

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)