Computing palindromic factorizations and palindromic covers on-line
Computing palindromic factorizations and palindromic covers on-line
复制标题
在线计算回文分解和回文覆盖
DOI：
10.1007/978-3-319-07566-2_16
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Tomohiro I;Shiho Sugimoto;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
字符串的回文子串分解是由w的回文子串组成的w的分解。在本文中，我们提出了一个在线的o (nlogn)-timeO(n)-空间算法来计算w的所有前缀的最小回文分解，其中w是给定字符串的长度。然后，我们展示了如何扩展该算法，以在线方式计算w的所有前缀的最小最大回文分解，仅包括每个前缀的最大回文（不可扩展的回文子串），inO（nlogn）时间和do (n)空间。我们还提出了一个在线eo (n)-timeO(n)-空间算法来计算w的最小回文覆盖。
Apalindromic factorizationof a stringwis a factorization ofwconsisting only of palindromic substrings ofw. In this paper, we present an on-lineO(nlogn)-timeO(n)-space algorithm to compute smallest palindromic factorizations of all prefixes ofw, wherenis the length of a given stringw. We then show how to extend this algorithm to compute smallest maximal palindromic factorizations of all prefixes ofw, consisting only of maximal palindromes (non-extensible palindromic substring) of each prefix, inO(nlogn) time andO(n) space, in an on-line manner. We also present an on-lineO(n)-timeO(n)-space algorithm to compute a smallest palindromic cover ofw.