Block Palindromes: A New Generalization of Palindromes
Block Palindromes: A New Generalization of Palindromes
复制标题
块回文：回文的新推广
DOI：
10.1007/978-3-030-00479-8_15
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Shunsuke Inenaga
中科院分区：
文献类型：
--
作者：
Keisuke Goto;Tomohiro I;Hideo Bannai;Shunsuke Inenaga
我们研究了一种新的回文和有间隙的回文的推广，称为块回文。块回文是当相同的子字符串被不同的字符替换时变成回文的字符串。我们研究了块回文的几个性质，特别是研究了块回文串的子串。在这样做的时候，我们引入了最大块回文的概念，这导致了一个紧凑的表示出现在一个字符串中的所有块回文。我们还提出了一个算法，它列举了所有的最大块回文出现在一个给定的stringintime，whereis的输出大小，这是最佳的，除非所有的最大块回文可以表示在一个更紧凑的方式。
We study a new generalization of palindromes and gapped palindromes calledblock 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 amaximal 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 stringintime, whereis the output size, which is optimal unless all the maximal block palindromes can be represented in a more compact way.