Palindromes are popular and important objects in textual data processing, bioinformatics, and combinatorics on words. Let $S = XaY$ be a string, where $X$ and $Y$ are of the same length and $a$ is either a single character or the empty string. Then, there exist two alternative definitions for palindromes: $S$ is said to be a palindrome if: Reversal-based definition: $S$ is equal to its reversal $S^R$; Symmetry-based definition: its left-arm $X$ is equal to the reversal of its right-arm $Y^R$. It is clear that if the "equality" ($\approx$) used in both definitions is exact character matching ($=$), then the two definitions are the same. However, if we apply other string-equality criteria $\approx$, including the complementary model for biological sequences, the parameterized model [Baker, JCSS 1996], the order-preserving model [Kim et al., TCS 2014], the Cartesian-tree model [Park et al., TCS 2020], and the palindromic-structure model [I et al., TCS 2013], then are the reversal-based palindromes and the symmetry-based palindromes the same? To the best of our knowledge, no previous work has considered or answered this natural question. In this paper, we first provide answers to this question, and then present efficient algorithms for computing all maximal generalized palindromes that occur in a given string. After confirming that Gusfield's offline suffix-tree based algorithm for computing maximal symmetry-based palindromes can be readily extended to the aforementioned matching models, we show how to extend Manacher's online algorithm for computing maximal reversal-based palindromes in linear time for all the aforementioned matching models.
翻译:Palindrome 是文本数据处理、生物信息学和词组组合中最受欢迎的重要对象。 让 $S = XAY$ 是一个字符串, 美元和美元为同一长度, 美元为单一字符或空字符串。 然后, 有两种关于 Palindrome 的替代定义 : 以 $S$ 表示是一个暗质质, 如果: 校正定义 : $S 等于其翻转 $S ; 校正法定义 : 其左臂 $X$ 等于其右臂 $X$ 等于其右臂 美元 $YQR$ 。 如果两个定义中使用的“ equality $\ a progrox ” 是精确字符匹配( =$), 那么两个定义是相同的。 但是, 如果我们应用其他的弦平标准 $\ apprealdroxx, 包括生物序列的补充模型[Baker, JCSS stroads basil, road- deal- smodemodemodel [Kyal salalal deal- deal deal deal deal deal deal deal deal deal deals], modelal demods the the the s mal deal deal deal deal demod.