A faster algorithm for computing maximal α-gapped repeats in a string

Yuka Tanimura; Yuta Fujishige; Tomohiro I; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda

doi:10.1007/978-3-319-23826-5_13

A faster algorithm for computing maximal α-gapped repeats in a string

Yuka Tanimura, Yuta Fujishige, Tomohiro I, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Mathematical Informatics

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

14 Citations (Scopus)

Abstract

A string x = uvu with both u, v being non-empty is called a gapped repeat with period p = |uv|, and is denoted by pair (x, p). If p ≤ α(|x| − p) with α > 1, then (x, p) is called an α-gapped repeat. An occurrence [i, i+|x|−1] of an α-gapped repeat (x, p) in a string w is called a maximal α-gapped repeat of w, if it cannot be extended either to the left or to the right in w with the same period p. Kolpakov et al. (CPM 2014) showed that, given a string of length n over a constant alphabet, all the occurrences of maximal α-gapped repeats in the string can be computed in O(α²n+occ) time, where occ is the number of occurrences. In this paper, we propose a faster O(αn + occ)-time algorithm to solve this problem, improving the result of Kolpakov et al. by a factor of α.

Original language	English
Title of host publication	String Processing and Information Retrieval - 22nd International Symposium, SPIRE 2015, Proceedings
Editors	Simon J. Puglisi, Costas S. Iliopoulos, Emine Yilmaz
Publisher	Springer Verlag
Pages	124-136
Number of pages	13
ISBN (Print)	9783319238258
DOIs	https://doi.org/10.1007/978-3-319-23826-5_13
Publication status	Published - 2015
Event	22nd International Symposium on String Processing and Information Retrieval, SPIRE 2015 - London, United Kingdom Duration: Sept 1 2015 → Sept 4 2015

Publication series

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

Other

Other	22nd International Symposium on String Processing and Information Retrieval, SPIRE 2015
Country/Territory	United Kingdom
City	London
Period	9/1/15 → 9/4/15

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-23826-5_13

Cite this

Tanimura, Y., Fujishige, Y., I, T., Inenaga, S., Bannai, H., & Takeda, M. (2015). A faster algorithm for computing maximal α-gapped repeats in a string. In S. J. Puglisi, C. S. Iliopoulos, & E. Yilmaz (Eds.), String Processing and Information Retrieval - 22nd International Symposium, SPIRE 2015, Proceedings (pp. 124-136). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9309). Springer Verlag. https://doi.org/10.1007/978-3-319-23826-5_13

A faster algorithm for computing maximal α-gapped repeats in a string. / Tanimura, Yuka; Fujishige, Yuta; I, Tomohiro et al.
String Processing and Information Retrieval - 22nd International Symposium, SPIRE 2015, Proceedings. ed. / Simon J. Puglisi; Costas S. Iliopoulos; Emine Yilmaz. Springer Verlag, 2015. p. 124-136 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9309).

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

Tanimura, Y, Fujishige, Y, I, T, Inenaga, S, Bannai, H & Takeda, M 2015, A faster algorithm for computing maximal α-gapped repeats in a string. in SJ Puglisi, CS Iliopoulos & E Yilmaz (eds), String Processing and Information Retrieval - 22nd International Symposium, SPIRE 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9309, Springer Verlag, pp. 124-136, 22nd International Symposium on String Processing and Information Retrieval, SPIRE 2015, London, United Kingdom, 9/1/15. https://doi.org/10.1007/978-3-319-23826-5_13

Tanimura Y, Fujishige Y, I T, Inenaga S, Bannai H, Takeda M. A faster algorithm for computing maximal α-gapped repeats in a string. In Puglisi SJ, Iliopoulos CS, Yilmaz E, editors, String Processing and Information Retrieval - 22nd International Symposium, SPIRE 2015, Proceedings. Springer Verlag. 2015. p. 124-136. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-23826-5_13

Tanimura, Yuka ; Fujishige, Yuta ; I, Tomohiro et al. / A faster algorithm for computing maximal α-gapped repeats in a string. String Processing and Information Retrieval - 22nd International Symposium, SPIRE 2015, Proceedings. editor / Simon J. Puglisi ; Costas S. Iliopoulos ; Emine Yilmaz. Springer Verlag, 2015. pp. 124-136 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4542ad7de9cc49968c502aa37ce1345a,

title = "A faster algorithm for computing maximal α-gapped repeats in a string",

abstract = "A string x = uvu with both u, v being non-empty is called a gapped repeat with period p = |uv|, and is denoted by pair (x, p). If p ≤ α(|x| − p) with α > 1, then (x, p) is called an α-gapped repeat. An occurrence [i, i+|x|−1] of an α-gapped repeat (x, p) in a string w is called a maximal α-gapped repeat of w, if it cannot be extended either to the left or to the right in w with the same period p. Kolpakov et al. (CPM 2014) showed that, given a string of length n over a constant alphabet, all the occurrences of maximal α-gapped repeats in the string can be computed in O(α2n+occ) time, where occ is the number of occurrences. In this paper, we propose a faster O(αn + occ)-time algorithm to solve this problem, improving the result of Kolpakov et al. by a factor of α.",

author = "Yuka Tanimura and Yuta Fujishige and Tomohiro I and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 22nd International Symposium on String Processing and Information Retrieval, SPIRE 2015 ; Conference date: 01-09-2015 Through 04-09-2015",

year = "2015",

doi = "10.1007/978-3-319-23826-5_13",

language = "English",

isbn = "9783319238258",

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

publisher = "Springer Verlag",

pages = "124--136",

editor = "Puglisi, {Simon J.} and Iliopoulos, {Costas S.} and Emine Yilmaz",

booktitle = "String Processing and Information Retrieval - 22nd International Symposium, SPIRE 2015, Proceedings",

address = "Germany",

}

TY - GEN

T1 - A faster algorithm for computing maximal α-gapped repeats in a string

AU - Tanimura, Yuka

AU - Fujishige, Yuta

AU - I, Tomohiro

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

PY - 2015

Y1 - 2015

N2 - A string x = uvu with both u, v being non-empty is called a gapped repeat with period p = |uv|, and is denoted by pair (x, p). If p ≤ α(|x| − p) with α > 1, then (x, p) is called an α-gapped repeat. An occurrence [i, i+|x|−1] of an α-gapped repeat (x, p) in a string w is called a maximal α-gapped repeat of w, if it cannot be extended either to the left or to the right in w with the same period p. Kolpakov et al. (CPM 2014) showed that, given a string of length n over a constant alphabet, all the occurrences of maximal α-gapped repeats in the string can be computed in O(α2n+occ) time, where occ is the number of occurrences. In this paper, we propose a faster O(αn + occ)-time algorithm to solve this problem, improving the result of Kolpakov et al. by a factor of α.

AB - A string x = uvu with both u, v being non-empty is called a gapped repeat with period p = |uv|, and is denoted by pair (x, p). If p ≤ α(|x| − p) with α > 1, then (x, p) is called an α-gapped repeat. An occurrence [i, i+|x|−1] of an α-gapped repeat (x, p) in a string w is called a maximal α-gapped repeat of w, if it cannot be extended either to the left or to the right in w with the same period p. Kolpakov et al. (CPM 2014) showed that, given a string of length n over a constant alphabet, all the occurrences of maximal α-gapped repeats in the string can be computed in O(α2n+occ) time, where occ is the number of occurrences. In this paper, we propose a faster O(αn + occ)-time algorithm to solve this problem, improving the result of Kolpakov et al. by a factor of α.

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

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

U2 - 10.1007/978-3-319-23826-5_13

DO - 10.1007/978-3-319-23826-5_13

M3 - Conference contribution

AN - SCOPUS:84944682942

SN - 9783319238258

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

SP - 124

EP - 136

BT - String Processing and Information Retrieval - 22nd International Symposium, SPIRE 2015, Proceedings

A2 - Puglisi, Simon J.

A2 - Iliopoulos, Costas S.

A2 - Yilmaz, Emine

PB - Springer Verlag

T2 - 22nd International Symposium on String Processing and Information Retrieval, SPIRE 2015

Y2 - 1 September 2015 through 4 September 2015

ER -

A faster algorithm for computing maximal α-gapped repeats in a string

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this