In-place algorithms for exact and approximate shortest unique substring problems
From MaRDI portal
(Redirected from In-place algorithms for exact and approximate shortest unique substring problems)
Publication:2399613
Publication:2399613
DOI10.1016/j.tcs.2017.05.032zbMath1371.68339arXiv1512.00378MaRDI 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
68W32: Algorithms on strings
Related Items
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, In-place algorithms for exact and approximate shortest unique substring problems, Space-time trade-offs for finding shortest unique substrings and maximal unique matches
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