Algorithms and combinatorial properties on shortest unique palindromic substrings
Algorithms and combinatorial properties on shortest unique palindromic substrings
复制标题
最短唯一回文子串的算法和组合属性
DOI：
10.1016/j.jda.2018.11.009
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Hiroe Inoue;Yuto Nakashima;Takuya Mieno;Shunsuke Inenaga;Hideo Bannai;Masayuki Takeda
回文是一个字符串，它的正反读都是一样的。一个字符串S的回文子串P被称为S中间隔为[s，t]的最短唯一回文子串（SUPS），如果P在S中只出现一次，则P的出现包含间隔[s，t]，并且S中包含间隔[s，t]且短于P的每个回文子串在S中至少出现两次。SUPS问题是，给定一个字符串S，对S进行预处理，以便对于任何后续查询间隔[s，t]，可以快速回答间隔[s，t]的所有SUPS。我们提出了一个最佳的解决方案，这个问题。也就是说，我们展示了如何在O（n）的时间和空间内预处理给定的长度为n的字符串S，以便在O（α+ 1）的时间内回答任何后续查询间隔的所有SUPS，其中α是输出的数量。我们还讨论了一个字符串中SUPS的数量。
A palindrome is a string that reads the same forward and backward. A palindromic substring P of a string S is called a shortest unique palindromic substring (SUPS) for an interval [s, t] in S, if P occurs exactly once in S, this occurrence of P contains interval [s, t], and every palindromic substring of S which contains interval [s, t] and is shorter than P occurs at least twice in S. The SUPS problem is, given a string S, to preprocess S so that for any subsequent query interval [s, t] all the SUPSs for interval [s, t] can be answered quickly. We present an optimal solution to this problem. Namely, we show how to preprocess a given string S of length n in O (n) time and space so that all SUPSs for any subsequent query interval can be answered in O (α+ 1) time, where α is the number of outputs. We also discuss the number of SUPSs in a string.
登录
查看更多内容
EERTREE：一种用于处理字符串中回文的高效数据结构
DOI：
--
发表时间：
2015
期刊：
European journal of combinatorics (Print)
影响因子：
--
作者：
Mikhail Rubinchik;A. Shur
通讯作者：
A. Shur
线性时间的回文长度
DOI：
10.4230/lipics.cpm.2017.23
发表时间：
2017
期刊：
--
影响因子：
--
作者：
K. Borozdin;D. Kosolobov;Mikhail Rubinchik;A. Shur
通讯作者：
A. Shur
用于精确和近似最短唯一子串问题的就地算法
DOI：
10.1016/j.tcs.2017.05.032
发表时间：
2017
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
W. Hon;Sharma V. Thankachan;Bojian Xu
通讯作者：
Bojian Xu
关于最短唯一子串查询
DOI：
10.1109/icde.2013.6544887
发表时间：
2013
期刊：
2013 IEEE 29th International Conference on Data Engineering (ICDE)
影响因子：
--
作者：
J. Pei;W. Wu;Mi
通讯作者：
Mi
DOI：
--
发表时间：
2014
期刊：
J. Discrete Algorithms
影响因子：
--
作者：
G. Fici;T. Gagie;Juha Kärkkäinen;Dominik Kempa
通讯作者：
Dominik Kempa