Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings
Fast Algorithms for the Shortest Unique Palindromic Substring Problem on Run-Length Encoded Strings
复制标题
游程编码字符串上最短唯一回文子串问题的快速算法
DOI：
10.1007/s00224-020-09980-x
复制
发表时间：
2020
影响因子：
0.5
通讯作者：
Takeda Masayuki
中科院分区：
文献类型：
--
作者：
Watanabe Kiichi;Nakashima Yuto;Inenaga Shunsuke;Bannai Hideo;Takeda Masayuki
对于字符串S，回文子字符串S [i. j]被称为S中区间[s，t]上最短的唯一回文子串（SUPS），如果S [i.. j]在S中只出现一次，区间[i，j]包含[s，t]，并且每个包含[s，t]的回文子串短于S [i. j]在S中至少出现两次。本文研究行程编码字符串上的SUPSqueries问题。我们展示了如何预处理一个给定的游程长度编码的字符串RLES的大小在O（m）空间和时间，使所有SUPS的任何后续查询间隔可以回答的时间，其中α是输出的数量，和是不同的运行的RLES的数量。此外，我们考虑的SUPS问题的一个变种，其中的查询间隔也给出了游程编码的形式。对于这个变种的问题，我们提出了两种替代算法更快的查询。第一个系统及时回答查询，可以及时构建，第二个系统及时回答查询，可以及时构建。这两种数据结构都需要O（m）空间。
For a stringS, a palindromic substringS[i..j] is said to be ashortest unique palindromic substring(SUPS) for an interval [s,t] inS, ifS[i..j] occurs exactly once inS, the interval [i,j] contains [s,t], and every palindromic substring containing [s,t] which is shorter thanS[i..j] occurs at least twice inS. In this paper, we study the problem of answeringSUPSqueries on run-length encoded strings. We show how to preprocess a given run-length encoded stringRLESof sizeminO(m) space andtime so that allSUPSsfor any subsequent query interval can be answered intime, whereαis the number of outputs, andis the number of distinct runs ofRLES. Additionaly, we consider a variant of the SUPS problem where a query interval is also given in a run-length encoded form. For this variant of the problem, we present two alternative algorithms with faster queries. The first one answers queries intime and can be built intime, and the second one answers queries intime and can be built intime. Both of these data structures requireO(m) space.