Scholars@Duke

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
Published version (DOI)

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

Jian Pei
Author Jian Pei Computer Science
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

10.1007/978-3-319-11918-2

EISSN

1611-3349

ISSN

0302-9743

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

10.1007/978-3-319-11918-2

EISSN

1611-3349

ISSN

0302-9743

Publication Date

January 1, 2014

Volume

8799

Start / End Page

161 / 172

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 46 Information and computing sciences