Shortest unique substring query revisited

DOI10.1007/978-3-319-07566-2_18MaRDI QIDQ5165603zbMATH OpenOpenAlexFDO

Authors Atalay M. Ileri, M. Oğuzhan Külekci, Bojian Xu

Publication date 30 June 2014

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.2738

zbMATH Keywords

regularityrepetitivenessshortest unique substring

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Abstract: We revisit the problem of finding shortest unique substring (SUS) proposed recently by [6]. We propose an optimal $O(n)$ time and space algorithm that can find an SUS for every location of a string of size $n$. Our algorithm significantly improves the $O(n^2)$ time complexity needed by [6]. We also support finding all the SUSes covering every location, whereas the solution in [6] can find only one SUS for every location. Further, our solution is simpler and easier to implement and can also be more space efficient in practice, since we only use the inverse suffix array and longest common prefix array of the string, while the algorithm in [6] uses the suffix tree of the string and other auxiliary data structures. Our theoretical results are validated by an empirical study that shows our algorithm is much faster and more space-saving than the one in [6].

Recommendations

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

Cited in

(15)

• Shortest unique palindromic substring queries in optimal time
• 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
• Shortest unique substrings queries in optimal time
• The Editor's Corner: Strings, Substrings, and the `Nearest Integer' Function
• 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
• scientific article; zbMATH DE number 7695992 (Why is no real title available?)
• Compact data structures for shortest unique substring queries
• Range shortest unique substring queries

This page was built for publication: Shortest unique substring query revisited

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