Shortest unique queries on strings
Publication
, Conference
Hu, X; Pei, J; Tao, Y
Published in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
January 1, 2014
Let D be a long input string of n characters (from an alphabet of size up to 2w, where w is the number of bits in a machine word). Given a substring q of D, a shortest unique query returns a shortest unique substring of D that contains q. We present an optimal structure that consumes O(n) space, can be built in O(n) time, and answers a query in O(1) time. We also extend our techniques to solve several variants of the problem optimally.
Duke Scholars
Altmetric Attention Stats
Dimensions Citation Stats
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
ISBN
9783319119175
Publication Date
January 1, 2014
Volume
8799
Start / End Page
161 / 172
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Hu, X., Pei, J., & Tao, Y. (2014). Shortest unique queries on strings. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 8799, pp. 161–172). https://doi.org/10.1007/978-3-319-11918-2
Hu, X., J. Pei, and Y. Tao. “Shortest unique queries on strings.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8799:161–72, 2014. https://doi.org/10.1007/978-3-319-11918-2.
Hu X, Pei J, Tao Y. Shortest unique queries on strings. In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2014. p. 161–72.
Hu, X., et al. “Shortest unique queries on strings.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8799, 2014, pp. 161–72. Scopus, doi:10.1007/978-3-319-11918-2.
Hu X, Pei J, Tao Y. Shortest unique queries on strings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2014. p. 161–172.
Published In
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
DOI
EISSN
1611-3349
ISSN
0302-9743
ISBN
9783319119175
Publication Date
January 1, 2014
Volume
8799
Start / End Page
161 / 172
Related Subject Headings
- Artificial Intelligence & Image Processing
- 46 Information and computing sciences