Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets

Noriki Fujisato; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda

doi:10.1007/978-3-030-32686-9_27

Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets

Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Mathematical Informatics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Citations (Scopus)

Abstract

We present the first worst-case linear time algorithm that directly computes the parameterized suffix and LCP arrays for constant sized alphabets. Previous algorithms either required quadratic time or the parameterized suffix tree to be built first. More formally, for a string over static alphabet and parameterized alphabet, our algorithm runs in time and O(n) words of space, where is the number of distinct symbols of in the string.

Original language	English
Title of host publication	String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Proceedings
Editors	Nieves R. Brisaboa, Simon J. Puglisi
Publisher	Springer
Pages	382-391
Number of pages	10
ISBN (Print)	9783030326852
DOIs	https://doi.org/10.1007/978-3-030-32686-9_27
Publication status	Published - 2019
Event	26th International Symposium on String Processing and Information Retrieval, SPIRE 2019 - Segovia, Spain Duration: Oct 7 2019 → Oct 9 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11811 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	26th International Symposium on String Processing and Information Retrieval, SPIRE 2019
Country/Territory	Spain
City	Segovia
Period	10/7/19 → 10/9/19

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-030-32686-9_27

Cite this

Fujisato, N., Nakashima, Y., Inenaga, S., Bannai, H., & Takeda, M. (2019). Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets. In N. R. Brisaboa, & S. J. Puglisi (Eds.), String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Proceedings (pp. 382-391). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11811 LNCS). Springer. https://doi.org/10.1007/978-3-030-32686-9_27

Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets. / Fujisato, Noriki; Nakashima, Yuto ; Inenaga, Shunsuke et al.
String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Proceedings. ed. / Nieves R. Brisaboa; Simon J. Puglisi. Springer, 2019. p. 382-391 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11811 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Fujisato, N, Nakashima, Y , Inenaga, S, Bannai, H & Takeda, M 2019, Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets. in NR Brisaboa & SJ Puglisi (eds), String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11811 LNCS, Springer, pp. 382-391, 26th International Symposium on String Processing and Information Retrieval, SPIRE 2019, Segovia, Spain, 10/7/19. https://doi.org/10.1007/978-3-030-32686-9_27

Fujisato N, Nakashima Y , Inenaga S, Bannai H, Takeda M. Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets. In Brisaboa NR, Puglisi SJ, editors, String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Proceedings. Springer. 2019. p. 382-391. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-32686-9_27

Fujisato, Noriki ; Nakashima, Yuto ; Inenaga, Shunsuke et al. / Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets. String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Proceedings. editor / Nieves R. Brisaboa ; Simon J. Puglisi. Springer, 2019. pp. 382-391 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{69d5457da9ad4440b8bf333cc280e889,

title = "Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets",

abstract = "We present the first worst-case linear time algorithm that directly computes the parameterized suffix and LCP arrays for constant sized alphabets. Previous algorithms either required quadratic time or the parameterized suffix tree to be built first. More formally, for a string over static alphabet and parameterized alphabet, our algorithm runs in time and O(n) words of space, where is the number of distinct symbols of in the string.",

author = "Noriki Fujisato and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 26th International Symposium on String Processing and Information Retrieval, SPIRE 2019 ; Conference date: 07-10-2019 Through 09-10-2019",

year = "2019",

doi = "10.1007/978-3-030-32686-9_27",

language = "English",

isbn = "9783030326852",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "382--391",

editor = "Brisaboa, {Nieves R.} and Puglisi, {Simon J.}",

booktitle = "String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Proceedings",

}

TY - GEN

T1 - Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets

AU - Fujisato, Noriki

AU - Nakashima, Yuto

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

PY - 2019

Y1 - 2019

N2 - We present the first worst-case linear time algorithm that directly computes the parameterized suffix and LCP arrays for constant sized alphabets. Previous algorithms either required quadratic time or the parameterized suffix tree to be built first. More formally, for a string over static alphabet and parameterized alphabet, our algorithm runs in time and O(n) words of space, where is the number of distinct symbols of in the string.

AB - We present the first worst-case linear time algorithm that directly computes the parameterized suffix and LCP arrays for constant sized alphabets. Previous algorithms either required quadratic time or the parameterized suffix tree to be built first. More formally, for a string over static alphabet and parameterized alphabet, our algorithm runs in time and O(n) words of space, where is the number of distinct symbols of in the string.

UR - http://www.scopus.com/inward/record.url?scp=85075686187&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075686187&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-32686-9_27

DO - 10.1007/978-3-030-32686-9_27

M3 - Conference contribution

AN - SCOPUS:85075686187

SN - 9783030326852

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 382

EP - 391

BT - String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Proceedings

A2 - Brisaboa, Nieves R.

A2 - Puglisi, Simon J.

PB - Springer

T2 - 26th International Symposium on String Processing and Information Retrieval, SPIRE 2019

Y2 - 7 October 2019 through 9 October 2019

ER -

Direct Linear Time Construction of Parameterized Suffix and LCP Arrays for Constant Alphabets

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this