In-place algorithms for exact and approximate shortest unique substring problems

DOI10.1016/j.tcs.2017.05.032zbMath1371.68339arXiv1512.00378OpenAlexW2621569787MaRDI QIDQ2399613

Sharma V. Thankachan, Wing-Kai Hon, Bojian Xu

Publication date: 24 August 2017

Published in: Theoretical Computer Science, Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

in-place algorithmsshortest unique substringstring pattern matching

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

In-place algorithms for exact and approximate shortest unique substring problems, Space-time trade-offs for finding shortest unique substrings and maximal unique matches, Space-efficient algorithms for computing minimal/shortest unique substrings, 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

Cites Work

• Unnamed Item
• A simple yet time-optimal and linear-space algorithm for shortest unique substring queries
• LCP array construction using \(O(\operatorname{sort}(n))\) (or less) I/Os
• In-place algorithms for exact and approximate shortest unique substring problems
• Shortest Unique Substrings Queries in Optimal Time
• Parallel External Memory Suffix Sorting
• Permuted Longest-Common-Prefix Array
• Fast Pattern Matching in Strings
• Faster External Memory LCP Array Construction
• Inducing Suffix and LCP Arrays in External Memory
• Engineering External Memory Induced Suffix Sorting