Name
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(vertical bar T vertical bar + parallel to MBP(T)parallel to) time, where parallel to MBP(T)parallel to is the output size, which is optimal unless all the maximal block palindromes can be represented in a more compact way. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-030-00479-8_15 | Lecture Notes in Computer Science |
Keywords | DocType | Volume |
Palindrome,Enumeration algorithm,Factorization | Conference | 11147 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
4 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Keisuke Goto | 1 | 98 | 13.93 |
| Tomohiro I | 2 | 148 | 22.06 |
| Hideo Bannai | 3 | 620 | 79.87 |
| Shunsuke Inenaga | 4 | 595 | 79.02 |