Recovering, counting and enumerating strings from forward and backward suffix arrays

Yuki Kuhara; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda

doi:10.1007/978-3-030-00479-8_21

Recovering, counting and enumerating strings from forward and backward suffix arrays

Yuki Kuhara, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Mathematical Informatics

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

1 Citation (Scopus)

Abstract

The suffix array SA_w of a string w of length n is a permutation of [1..n] such that SA_w[i]=j iff w[j, n] is the lexicographically i-th suffix of w. In this paper, we consider variants of the reverse-engineering problem on suffix arrays with two given permutations P and Q of [1..n], such that P refers to the forward suffix array of some string w and Q refers to the backward suffix array of the reversed string w^R. Our results are the following: (1) An algorithm which computes a solution string over an alphabet of the smallest size, in O(n) time. (2) The exact number of solution strings over an alphabet of size σ. (3) An efficient algorithm which computes all solution strings in the lexicographical order, in time near optimal up to log n factor.

Original language	English
Title of host publication	String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings
Editors	Travis Gagie, Alistair Moffat, Gonzalo Navarro, Ernesto Cuadros-Vargas
Publisher	Springer Verlag
Pages	254-267
Number of pages	14
ISBN (Print)	9783030004781
DOIs	https://doi.org/10.1007/978-3-030-00479-8_21
Publication status	Published - 2018
Event	25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 - Lima, Peru Duration: Oct 9 2018 → Oct 11 2018

Publication series

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

Other

Other	25th International Symposium on String Processing and Information Retrieval, SPIRE 2018
Country/Territory	Peru
City	Lima
Period	10/9/18 → 10/11/18

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-030-00479-8_21

Cite this

Kuhara, Y., Nakashima, Y., Inenaga, S., Bannai, H., & Takeda, M. (2018). Recovering, counting and enumerating strings from forward and backward suffix arrays. In T. Gagie, A. Moffat, G. Navarro, & E. Cuadros-Vargas (Eds.), String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings (pp. 254-267). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11147 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-00479-8_21

Recovering, counting and enumerating strings from forward and backward suffix arrays. / Kuhara, Yuki; Nakashima, Yuto ; Inenaga, Shunsuke et al.
String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. ed. / Travis Gagie; Alistair Moffat; Gonzalo Navarro; Ernesto Cuadros-Vargas. Springer Verlag, 2018. p. 254-267 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11147 LNCS).

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

Kuhara, Y, Nakashima, Y , Inenaga, S, Bannai, H & Takeda, M 2018, Recovering, counting and enumerating strings from forward and backward suffix arrays. in T Gagie, A Moffat, G Navarro & E Cuadros-Vargas (eds), String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11147 LNCS, Springer Verlag, pp. 254-267, 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018, Lima, Peru, 10/9/18. https://doi.org/10.1007/978-3-030-00479-8_21

Kuhara Y, Nakashima Y , Inenaga S, Bannai H, Takeda M. Recovering, counting and enumerating strings from forward and backward suffix arrays. In Gagie T, Moffat A, Navarro G, Cuadros-Vargas E, editors, String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. Springer Verlag. 2018. p. 254-267. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-00479-8_21

Kuhara, Yuki ; Nakashima, Yuto ; Inenaga, Shunsuke et al. / Recovering, counting and enumerating strings from forward and backward suffix arrays. String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. editor / Travis Gagie ; Alistair Moffat ; Gonzalo Navarro ; Ernesto Cuadros-Vargas. Springer Verlag, 2018. pp. 254-267 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c66a28d5527b4de69a468b72febc6910,

title = "Recovering, counting and enumerating strings from forward and backward suffix arrays",

abstract = "The suffix array SAw of a string w of length n is a permutation of [1..n] such that SAw[i]=j iff w[j, n] is the lexicographically i-th suffix of w. In this paper, we consider variants of the reverse-engineering problem on suffix arrays with two given permutations P and Q of [1..n], such that P refers to the forward suffix array of some string w and Q refers to the backward suffix array of the reversed string wR. Our results are the following: (1) An algorithm which computes a solution string over an alphabet of the smallest size, in O(n) time. (2) The exact number of solution strings over an alphabet of size σ. (3) An efficient algorithm which computes all solution strings in the lexicographical order, in time near optimal up to log n factor.",

author = "Yuki Kuhara and Yuto Nakashima and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda",

note = "Funding Information: Acknowledgments. This work was supported by JSPS KAKENHI Grant Numbers JP18K18002 (YN), JP17H01697 (SI), JP16H02783 (HB), and JP18H04098 (MT). Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2018.; 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018 ; Conference date: 09-10-2018 Through 11-10-2018",

year = "2018",

doi = "10.1007/978-3-030-00479-8_21",

language = "English",

isbn = "9783030004781",

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

publisher = "Springer Verlag",

pages = "254--267",

editor = "Travis Gagie and Alistair Moffat and Gonzalo Navarro and Ernesto Cuadros-Vargas",

booktitle = "String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Recovering, counting and enumerating strings from forward and backward suffix arrays

AU - Kuhara, Yuki

AU - Nakashima, Yuto

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

N1 - Funding Information: Acknowledgments. This work was supported by JSPS KAKENHI Grant Numbers JP18K18002 (YN), JP17H01697 (SI), JP16H02783 (HB), and JP18H04098 (MT). Publisher Copyright: © Springer Nature Switzerland AG 2018.

PY - 2018

Y1 - 2018

N2 - The suffix array SAw of a string w of length n is a permutation of [1..n] such that SAw[i]=j iff w[j, n] is the lexicographically i-th suffix of w. In this paper, we consider variants of the reverse-engineering problem on suffix arrays with two given permutations P and Q of [1..n], such that P refers to the forward suffix array of some string w and Q refers to the backward suffix array of the reversed string wR. Our results are the following: (1) An algorithm which computes a solution string over an alphabet of the smallest size, in O(n) time. (2) The exact number of solution strings over an alphabet of size σ. (3) An efficient algorithm which computes all solution strings in the lexicographical order, in time near optimal up to log n factor.

AB - The suffix array SAw of a string w of length n is a permutation of [1..n] such that SAw[i]=j iff w[j, n] is the lexicographically i-th suffix of w. In this paper, we consider variants of the reverse-engineering problem on suffix arrays with two given permutations P and Q of [1..n], such that P refers to the forward suffix array of some string w and Q refers to the backward suffix array of the reversed string wR. Our results are the following: (1) An algorithm which computes a solution string over an alphabet of the smallest size, in O(n) time. (2) The exact number of solution strings over an alphabet of size σ. (3) An efficient algorithm which computes all solution strings in the lexicographical order, in time near optimal up to log n factor.

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

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

U2 - 10.1007/978-3-030-00479-8_21

DO - 10.1007/978-3-030-00479-8_21

M3 - Conference contribution

AN - SCOPUS:85054817708

SN - 9783030004781

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

SP - 254

EP - 267

BT - String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings

A2 - Gagie, Travis

A2 - Moffat, Alistair

A2 - Navarro, Gonzalo

A2 - Cuadros-Vargas, Ernesto

PB - Springer Verlag

T2 - 25th International Symposium on String Processing and Information Retrieval, SPIRE 2018

Y2 - 9 October 2018 through 11 October 2018

ER -

Recovering, counting and enumerating strings from forward and backward suffix arrays

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this