Shortest Unique Palindromic Substring Queries in Optimal Time
Shortest Unique Palindromic Substring Queries in Optimal Time
复制标题
最佳时间的最短唯一回文子串查询
DOI：
10.1007/978-3-319-78825-8_32
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Yuto Nakashima;Takuya Takagi;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
回文是向前和向后读相同的字符串。一个字符串S的回文子串P称为区间[S，t]INS的最短唯一回文子串($$SUPS$$)，如果P恰好出现一次INS，则此P包含区间[S，t]，且每个包含区间[S，t]且短于P的回文子串至少出现两次。给出一个字符串，对$$SUPS$$问题进行预处理，以便对于任何后续的查询间隔[S，t]，可以快速地回答间隔[S，t]的所有$$SUPS\Text{S}$$。我们给出了这个问题的最优解。也就是说，我们展示了如何对给定的长度为O(N)的时间和空间的字符串进行预处理，使得任何后续查询间隔的所有$$SUPS\TEXT{S}$$都可以在$$O(\α+1)$$时间内得到回答，其中$$\α$$是输出的数目。
A palindrome is a string that reads the same forward and backward. A palindromic substringPof a stringSis called a shortest unique palindromic substring ($$ SUPS $$) for an interval [s,t] inS, ifPoccurs exactly once inS, this occurrence ofPcontains interval [s,t], and every palindromic substring ofSwhich contains interval [s,t] and is shorter thanPoccurs at least twice inS. The $$ SUPS $$ problem is, given a stringS, to preprocessSso that for any subsequent query interval [s,t] all the $$ SUPS \text {s}$$ for interval [s,t] can be answered quickly. We present an optimal solution to this problem. Namely, we show how to preprocess a given stringSof lengthninO(n) time and space so that all $$ SUPS \text {s}$$ for any subsequent query interval can be answered in $$O(\alpha + 1)$$ time, where $$\alpha $$ is the number of outputs.