2018/06/01 by Goto, Keisuke, I, Tomohiro, Bannai, Hideo +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1806.00198
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.