Block palindromes: A new generalization of palindromes

Keisuke Goto; Tomohiro I; Hideo Bannai; Shunsuke Inenaga

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

Block palindromes: A new generalization of palindromes

Keisuke Goto, Tomohiro I, Hideo Bannai, Shunsuke Inenaga

Mathematical Informatics

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

1 Citation (Scopus)

Abstract

We study a new generalization of palindromes and gapped palindromes called block palindromes. A block palindrome is a string that becomes a palindrome when identical substrings are replaced with a distinct character. We investigate several properties of block palindromes and in particular, study substrings of a string which are block palindromes. In so doing, we introduce the notion of a maximal block palindrome, which leads to a compact representation of all block palindromes that occur in a string. We also propose an algorithm which enumerates all maximal block palindromes that appear in a given string T in O(|T|+||MBP(T)||) time, where ||MBP(T)|| is the output size, which is optimal unless all the maximal block palindromes can be represented in a more compact way.

Original language	English
Title of host publication	String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings
Editors	Travis Gagie, Alistair Moffat, Ernesto Cuadros-Vargas, Gonzalo Navarro
Publisher	Springer Verlag
Pages	183-190
Number of pages	8
ISBN (Print)	9783030004781
DOIs	https://doi.org/10.1007/978-3-030-00479-8_15
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_15

Cite this

Goto, K., I, T., Bannai, H., & Inenaga, S. (2018). Block palindromes: A new generalization of palindromes. In T. Gagie, A. Moffat, E. Cuadros-Vargas, & G. Navarro (Eds.), String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings (pp. 183-190). (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_15

Block palindromes: A new generalization of palindromes. / Goto, Keisuke; I, Tomohiro; Bannai, Hideo et al.
String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. ed. / Travis Gagie; Alistair Moffat; Ernesto Cuadros-Vargas; Gonzalo Navarro. Springer Verlag, 2018. p. 183-190 (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

Goto, K, I, T, Bannai, H & Inenaga, S 2018, Block palindromes: A new generalization of palindromes. in T Gagie, A Moffat, E Cuadros-Vargas & G Navarro (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. 183-190, 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_15

Goto K, I T, Bannai H, Inenaga S. Block palindromes: A new generalization of palindromes. In Gagie T, Moffat A, Cuadros-Vargas E, Navarro G, editors, String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. Springer Verlag. 2018. p. 183-190. (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_15

Goto, Keisuke ; I, Tomohiro ; Bannai, Hideo et al. / Block palindromes : A new generalization of palindromes. String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Proceedings. editor / Travis Gagie ; Alistair Moffat ; Ernesto Cuadros-Vargas ; Gonzalo Navarro. Springer Verlag, 2018. pp. 183-190 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{12605f6accdd41488909ace2503c0f80,

title = "Block palindromes: A new generalization of palindromes",

abstract = "We study a new generalization of palindromes and gapped palindromes called block palindromes. A block palindrome is a string that becomes a palindrome when identical substrings are replaced with a distinct character. We investigate several properties of block palindromes and in particular, study substrings of a string which are block palindromes. In so doing, we introduce the notion of a maximal block palindrome, which leads to a compact representation of all block palindromes that occur in a string. We also propose an algorithm which enumerates all maximal block palindromes that appear in a given string T in O(|T|+||MBP(T)||) time, where ||MBP(T)|| is the output size, which is optimal unless all the maximal block palindromes can be represented in a more compact way.",

author = "Keisuke Goto and Tomohiro I and Hideo Bannai and Shunsuke Inenaga",

note = "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_15",

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 = "183--190",

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

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

address = "Germany",

}

TY - GEN

T1 - Block palindromes

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

AU - Goto, Keisuke

AU - I, Tomohiro

AU - Bannai, Hideo

AU - Inenaga, Shunsuke

PY - 2018

Y1 - 2018

N2 - We study a new generalization of palindromes and gapped palindromes called block palindromes. A block palindrome is a string that becomes a palindrome when identical substrings are replaced with a distinct character. We investigate several properties of block palindromes and in particular, study substrings of a string which are block palindromes. In so doing, we introduce the notion of a maximal block palindrome, which leads to a compact representation of all block palindromes that occur in a string. We also propose an algorithm which enumerates all maximal block palindromes that appear in a given string T in O(|T|+||MBP(T)||) time, where ||MBP(T)|| is the output size, which is optimal unless all the maximal block palindromes can be represented in a more compact way.

AB - We study a new generalization of palindromes and gapped palindromes called block palindromes. A block palindrome is a string that becomes a palindrome when identical substrings are replaced with a distinct character. We investigate several properties of block palindromes and in particular, study substrings of a string which are block palindromes. In so doing, we introduce the notion of a maximal block palindrome, which leads to a compact representation of all block palindromes that occur in a string. We also propose an algorithm which enumerates all maximal block palindromes that appear in a given string T in O(|T|+||MBP(T)||) time, where ||MBP(T)|| is the output size, which is optimal unless all the maximal block palindromes can be represented in a more compact way.

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

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

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

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

M3 - Conference contribution

AN - SCOPUS:85054822428

SN - 9783030004781

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

SP - 183

EP - 190

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

A2 - Gagie, Travis

A2 - Moffat, Alistair

A2 - Cuadros-Vargas, Ernesto

A2 - Navarro, Gonzalo

PB - Springer Verlag

Y2 - 9 October 2018 through 11 October 2018

ER -

Block palindromes: A new generalization of palindromes

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this