A simple yet time-optimal and linear-space algorithm for shortest unique substring queries

DOI10.1016/j.tcs.2014.11.004zbMath1303.68163OpenAlexW2040322457MaRDI QIDQ476914

Atalay Mert İleri, Bojian Xu, M. Oğuzhan Külekci

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.11.004

zbMATH Keywords

regularityrepetitivenessshortest unique substringunique substring

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

In-place algorithms for exact and approximate shortest unique substring problems, Space-efficient algorithms for computing minimal/shortest unique substrings, Computing minimal unique substrings for a sliding window

Uses Software

• REPuter

Cites Work

• Unnamed Item
• Computing regularities in strings: a survey
• Space efficient linear time construction of suffix arrays
• Shortest Unique Substrings Queries in Optimal Time
• Minimum Unique Substrings and Maximum Repeats
• Algorithms on Strings, Trees and Sequences
• Jewels of Stringology
• Shortest Unique Substring Query Revisited