Shortest unique substrings queries in optimal time

DOI10.1007/978-3-319-04298-5_44MaRDI QIDQ2938125zbMATH OpenOpenAlexFDO

Authors Kazuya Tsuruta, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Publication date 13 January 2015

Published in SOFSEM 2014: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-04298-5_44

Mathematics Subject Classification ID

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

Recommendations

• A simple yet time-optimal and linear-space algorithm for shortest unique substring queries
• Shortest unique substring query revisited
• Space-time trade-offs for the shortest unique substring problem
• Space-time trade-offs for finding shortest unique substrings and maximal unique matches
• Space-efficient algorithms for computing minimal/shortest unique substrings

Cited in

(16)

• Algorithms and combinatorial properties on shortest unique palindromic substrings
• Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings
• Computing minimal unique substrings for a sliding window
• Space-efficient algorithms for computing minimal/shortest unique substrings
• Space-time trade-offs for finding shortest unique substrings and maximal unique matches
• Minimum unique substrings and maximum repeats
• Minimal Unique Substrings and Minimal Absent Words in a Sliding Window
• Shortest Unique Substring Queries on Run-Length Encoded Strings
• Space-time trade-offs for the shortest unique substring problem
• A simple yet time-optimal and linear-space algorithm for shortest unique substring queries
• Tight bounds on the maximum number of shortest unique substrings
• Shortest unique substring query revisited
• Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.
• Data structures for computing unique palindromes in static and non-static strings
• Compact data structures for shortest unique substring queries
• Range shortest unique substring queries

This page was built for publication: Shortest unique substrings queries in optimal time

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