Computing palindromic factorizations and palindromic covers on-line

Tomohiro I; Shiho Sugimoto; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda

doi:10.1007/978-3-319-07566-2_16

Computing palindromic factorizations and palindromic covers on-line

Tomohiro I, Shiho Sugimoto, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

Mathematical Informatics

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

30 Citations (Scopus)

Abstract

A palindromic factorization of a string w is a factorization of w consisting only of palindromic substrings of w. In this paper, we present an on-line O(n logn)-time O(n)-space algorithm to compute smallest palindromic factorizations of all prefixes of w, where n is the length of a given string w. We then show how to extend this algorithm to compute smallest maximal palindromic factorizations of all prefixes of w, consisting only of maximal palindromes (non-extensible palindromic substring) of each prefix, in O(n logn) time and O(n) space, in an on-line manner. We also present an on-line O(n)-time O(n)-space algorithm to compute a smallest palindromic cover of w.

Original language	English
Title of host publication	Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings
Publisher	Springer Verlag
Pages	150-161
Number of pages	12
ISBN (Print)	9783319075655
DOIs	https://doi.org/10.1007/978-3-319-07566-2_16
Publication status	Published - 2014
Event	25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014 - Moscow, Russian Federation Duration: Jun 16 2014 → Jun 18 2014

Publication series

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

Other

Other	25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014
Country/Territory	Russian Federation
City	Moscow
Period	6/16/14 → 6/18/14

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-07566-2_16

Cite this

I, T., Sugimoto, S., Inenaga, S., Bannai, H., & Takeda, M. (2014). Computing palindromic factorizations and palindromic covers on-line. In Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings (pp. 150-161). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8486). Springer Verlag. https://doi.org/10.1007/978-3-319-07566-2_16

Computing palindromic factorizations and palindromic covers on-line. / I, Tomohiro; Sugimoto, Shiho; Inenaga, Shunsuke et al.
Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings. Springer Verlag, 2014. p. 150-161 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8486).

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

I, T, Sugimoto, S, Inenaga, S, Bannai, H & Takeda, M 2014, Computing palindromic factorizations and palindromic covers on-line. in Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8486, Springer Verlag, pp. 150-161, 25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014, Moscow, Russian Federation, 6/16/14. https://doi.org/10.1007/978-3-319-07566-2_16

I T, Sugimoto S, Inenaga S, Bannai H, Takeda M. Computing palindromic factorizations and palindromic covers on-line. In Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings. Springer Verlag. 2014. p. 150-161. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-07566-2_16

I, Tomohiro ; Sugimoto, Shiho ; Inenaga, Shunsuke et al. / Computing palindromic factorizations and palindromic covers on-line. Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings. Springer Verlag, 2014. pp. 150-161 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{83aec1bb1f5f4ddc80030a7a50917bd6,

title = "Computing palindromic factorizations and palindromic covers on-line",

abstract = "A palindromic factorization of a string w is a factorization of w consisting only of palindromic substrings of w. In this paper, we present an on-line O(n logn)-time O(n)-space algorithm to compute smallest palindromic factorizations of all prefixes of w, where n is the length of a given string w. We then show how to extend this algorithm to compute smallest maximal palindromic factorizations of all prefixes of w, consisting only of maximal palindromes (non-extensible palindromic substring) of each prefix, in O(n logn) time and O(n) space, in an on-line manner. We also present an on-line O(n)-time O(n)-space algorithm to compute a smallest palindromic cover of w.",

author = "Tomohiro I and Shiho Sugimoto and Shunsuke Inenaga and Hideo Bannai and Masayuki Takeda",

year = "2014",

doi = "10.1007/978-3-319-07566-2_16",

language = "English",

isbn = "9783319075655",

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

publisher = "Springer Verlag",

pages = "150--161",

booktitle = "Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings",

address = "Germany",

note = "25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014 ; Conference date: 16-06-2014 Through 18-06-2014",

}

TY - GEN

T1 - Computing palindromic factorizations and palindromic covers on-line

AU - I, Tomohiro

AU - Sugimoto, Shiho

AU - Inenaga, Shunsuke

AU - Bannai, Hideo

AU - Takeda, Masayuki

PY - 2014

Y1 - 2014

N2 - A palindromic factorization of a string w is a factorization of w consisting only of palindromic substrings of w. In this paper, we present an on-line O(n logn)-time O(n)-space algorithm to compute smallest palindromic factorizations of all prefixes of w, where n is the length of a given string w. We then show how to extend this algorithm to compute smallest maximal palindromic factorizations of all prefixes of w, consisting only of maximal palindromes (non-extensible palindromic substring) of each prefix, in O(n logn) time and O(n) space, in an on-line manner. We also present an on-line O(n)-time O(n)-space algorithm to compute a smallest palindromic cover of w.

AB - A palindromic factorization of a string w is a factorization of w consisting only of palindromic substrings of w. In this paper, we present an on-line O(n logn)-time O(n)-space algorithm to compute smallest palindromic factorizations of all prefixes of w, where n is the length of a given string w. We then show how to extend this algorithm to compute smallest maximal palindromic factorizations of all prefixes of w, consisting only of maximal palindromes (non-extensible palindromic substring) of each prefix, in O(n logn) time and O(n) space, in an on-line manner. We also present an on-line O(n)-time O(n)-space algorithm to compute a smallest palindromic cover of w.

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

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

U2 - 10.1007/978-3-319-07566-2_16

DO - 10.1007/978-3-319-07566-2_16

M3 - Conference contribution

AN - SCOPUS:84958527699

SN - 9783319075655

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

SP - 150

EP - 161

BT - Combinatorial Pattern Matching - 25th Annual Symposium, CPM 2014, Proceedings

PB - Springer Verlag

T2 - 25th Annual Symposium on Combinatorial Pattern Matching, CPM 2014

Y2 - 16 June 2014 through 18 June 2014

ER -

Computing palindromic factorizations and palindromic covers on-line

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this