Solving the String Statistics Problem in Time O(n log n)

Gerth Stølting Brodal; Rune B. Lyngsø; Anna Östlin; Christian Nørgaard Storm Pedersen

doi:10.1007/3-540-45465-9_62

Solving the String Statistics Problem in Time O(n log n)

Gerth Stølting Brodal, Rune B. Lyngsø, Anna Östlin, Christian Nørgaard Storm Pedersen

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

23 Citations (Scopus)

Abstract

The string statistics problem consists of preprocessing a string of length n such that given a query pattern of length m, the maximum number of non-overlapping occurrences of the query pattern in the string can be reported efficiently. Apostolico and Preparata introduced the minimal augmented suffix tree (MAST) as a data structure for the string statistics problem, and showed how to construct the MAST in time (nlog² n) and how it supports queries in time (m) for constant sized alphabets. A subsequent theorem by Fraenkel and Simpson stating that a string has at most a linear number of distinct squares implies that the MAST requires space (n). In this paper we improve the construction time for the MAST to (nlogn) by extending the algorithm of Apostolico and Preparata to exploit properties of efficient joining and splitting of search trees together with a refined analysis. Partially supported by the Future and Emerging Technologies programme of the EU under contract number IST-1999-14186 (ALCOM-FT).Supported by the Carlsberg Foundation (contract number ANS-0257/20).Basic Research in Computer Science (BRICS), www.brics.dk, funded by the Danish National Research Foundation.Bioinformatics Research Center (BiRC), www.birc.dk, funded by Aarhus University Research Fundation.

Original language	English
Title of host publication	Automata, Languages and Programming : 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8–13, 2002 Proceedings
Editors	Peter Widmayer, Stephan Eidenbenz, Francisco Triguero, Rafael Morales, Ricardo Conejo, Matthew Hennessy
Number of pages	12
Publisher	Springer
Publication date	2002
Pages	728-739
ISBN (Print)	978-3-540-43864-5
DOIs	https://doi.org/10.1007/3-540-45465-9_62
Publication status	Published - 2002
Event	29th International Colloquium, ICALP 2002 - Málaga, Spain Duration: 8 Jul 2002 → 13 Jul 2002 Conference number: 29

Conference

Conference	29th International Colloquium, ICALP 2002
Number	29
Country/Territory	Spain
City	Málaga
Period	08/07/2002 → 13/07/2002

Series	Lecture Notes in Computer Science
Volume	2380
ISSN	0302-9743

Access to Document

10.1007/3-540-45465-9_62

Cite this

Brodal, G. S., Lyngsø, R. B., Östlin, A., & Pedersen, C. N. S. (2002). Solving the String Statistics Problem in Time O(n log n). In P. Widmayer, S. Eidenbenz, F. Triguero, R. Morales, R. Conejo, & M. Hennessy (Eds.), Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8–13, 2002 Proceedings (pp. 728-739). Springer. https://doi.org/10.1007/3-540-45465-9_62

Brodal, Gerth Stølting ; Lyngsø, Rune B. ; Östlin, Anna et al. / Solving the String Statistics Problem in Time O(n log n). Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8–13, 2002 Proceedings. editor / Peter Widmayer ; Stephan Eidenbenz ; Francisco Triguero ; Rafael Morales ; Ricardo Conejo ; Matthew Hennessy. Springer, 2002. pp. 728-739 (Lecture Notes in Computer Science, Vol. 2380).

@inproceedings{d2688ad0983b11dabee902004c4f4f50,

title = "Solving the String Statistics Problem in Time O(n log n)",

abstract = "The string statistics problem consists of preprocessing a string of length n such that given a query pattern of length m, the maximum number of non-overlapping occurrences of the query pattern in the string can be reported efficiently. Apostolico and Preparata introduced the minimal augmented suffix tree (MAST) as a data structure for the string statistics problem, and showed how to construct the MAST in time (nlog2 n) and how it supports queries in time (m) for constant sized alphabets. A subsequent theorem by Fraenkel and Simpson stating that a string has at most a linear number of distinct squares implies that the MAST requires space (n). In this paper we improve the construction time for the MAST to (nlogn) by extending the algorithm of Apostolico and Preparata to exploit properties of efficient joining and splitting of search trees together with a refined analysis. Partially supported by the Future and Emerging Technologies programme of the EU under contract number IST-1999-14186 (ALCOM-FT).Supported by the Carlsberg Foundation (contract number ANS-0257/20).Basic Research in Computer Science (BRICS), www.brics.dk, funded by the Danish National Research Foundation.Bioinformatics Research Center (BiRC), www.birc.dk, funded by Aarhus University Research Fundation.",

author = "Brodal, {Gerth St{\o}lting} and Lyngs{\o}, {Rune B.} and Anna {\"O}stlin and Pedersen, {Christian N{\o}rgaard Storm}",

year = "2002",

doi = "10.1007/3-540-45465-9_62",

language = "English",

isbn = "978-3-540-43864-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "728--739",

editor = "Peter Widmayer and Stephan Eidenbenz and Francisco Triguero and Rafael Morales and Ricardo Conejo and Matthew Hennessy",

booktitle = "Automata, Languages and Programming",

address = "Netherlands",

note = "29th International Colloquium, ICALP 2002 ; Conference date: 08-07-2002 Through 13-07-2002",

}

Brodal, GS, Lyngsø, RB, Östlin, A & Pedersen, CNS 2002, Solving the String Statistics Problem in Time O(n log n). in P Widmayer, S Eidenbenz, F Triguero, R Morales, R Conejo & M Hennessy (eds), Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8–13, 2002 Proceedings. Springer, Lecture Notes in Computer Science, vol. 2380, pp. 728-739, 29th International Colloquium, ICALP 2002, Málaga, Spain, 08/07/2002. https://doi.org/10.1007/3-540-45465-9_62

Solving the String Statistics Problem in Time O(n log n). / Brodal, Gerth Stølting; Lyngsø, Rune B.; Östlin, Anna et al.
Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8–13, 2002 Proceedings. ed. / Peter Widmayer; Stephan Eidenbenz; Francisco Triguero; Rafael Morales; Ricardo Conejo; Matthew Hennessy. Springer, 2002. p. 728-739 (Lecture Notes in Computer Science, Vol. 2380).

Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Solving the String Statistics Problem in Time O(n log n)

AU - Brodal, Gerth Stølting

AU - Lyngsø, Rune B.

AU - Östlin, Anna

AU - Pedersen, Christian Nørgaard Storm

N1 - Conference code: 29

PY - 2002

Y1 - 2002

N2 - The string statistics problem consists of preprocessing a string of length n such that given a query pattern of length m, the maximum number of non-overlapping occurrences of the query pattern in the string can be reported efficiently. Apostolico and Preparata introduced the minimal augmented suffix tree (MAST) as a data structure for the string statistics problem, and showed how to construct the MAST in time (nlog2 n) and how it supports queries in time (m) for constant sized alphabets. A subsequent theorem by Fraenkel and Simpson stating that a string has at most a linear number of distinct squares implies that the MAST requires space (n). In this paper we improve the construction time for the MAST to (nlogn) by extending the algorithm of Apostolico and Preparata to exploit properties of efficient joining and splitting of search trees together with a refined analysis. Partially supported by the Future and Emerging Technologies programme of the EU under contract number IST-1999-14186 (ALCOM-FT).Supported by the Carlsberg Foundation (contract number ANS-0257/20).Basic Research in Computer Science (BRICS), www.brics.dk, funded by the Danish National Research Foundation.Bioinformatics Research Center (BiRC), www.birc.dk, funded by Aarhus University Research Fundation.

AB - The string statistics problem consists of preprocessing a string of length n such that given a query pattern of length m, the maximum number of non-overlapping occurrences of the query pattern in the string can be reported efficiently. Apostolico and Preparata introduced the minimal augmented suffix tree (MAST) as a data structure for the string statistics problem, and showed how to construct the MAST in time (nlog2 n) and how it supports queries in time (m) for constant sized alphabets. A subsequent theorem by Fraenkel and Simpson stating that a string has at most a linear number of distinct squares implies that the MAST requires space (n). In this paper we improve the construction time for the MAST to (nlogn) by extending the algorithm of Apostolico and Preparata to exploit properties of efficient joining and splitting of search trees together with a refined analysis. Partially supported by the Future and Emerging Technologies programme of the EU under contract number IST-1999-14186 (ALCOM-FT).Supported by the Carlsberg Foundation (contract number ANS-0257/20).Basic Research in Computer Science (BRICS), www.brics.dk, funded by the Danish National Research Foundation.Bioinformatics Research Center (BiRC), www.birc.dk, funded by Aarhus University Research Fundation.

U2 - 10.1007/3-540-45465-9_62

DO - 10.1007/3-540-45465-9_62

M3 - Article in proceedings

SN - 978-3-540-43864-5

T3 - Lecture Notes in Computer Science

SP - 728

EP - 739

BT - Automata, Languages and Programming

A2 - Widmayer, Peter

A2 - Eidenbenz, Stephan

A2 - Triguero, Francisco

A2 - Morales, Rafael

A2 - Conejo, Ricardo

A2 - Hennessy, Matthew

PB - Springer

T2 - 29th International Colloquium, ICALP 2002

Y2 - 8 July 2002 through 13 July 2002

ER -

Brodal GS, Lyngsø RB, Östlin A, Pedersen CNS. Solving the String Statistics Problem in Time O(n log n). In Widmayer P, Eidenbenz S, Triguero F, Morales R, Conejo R, Hennessy M, editors, Automata, Languages and Programming: 29th International Colloquium, ICALP 2002 Málaga, Spain, July 8–13, 2002 Proceedings. Springer. 2002. p. 728-739. (Lecture Notes in Computer Science, Vol. 2380). doi: 10.1007/3-540-45465-9_62

Solving the String Statistics Problem in Time O(n log n)

Abstract

Conference

Access to Document

Fingerprint

Cite this