Finding Distinct Subpalindromes Online

Finding Distinct Subpalindromes Online
复制标题

在线查找不同的子回文

DOI：
--
复制
发表时间：
2013
期刊：
--
影响因子：
--
通讯作者：
A. Shur
A. Shur
中科院分区：
--
文献类型：
--
作者：
D. Kosolobov;Mikhail Rubinchik;A. Shur

文献摘要

被引文献

相似文献

我们展示了一种在线算法，可以通过有序的字母来找到给定的字符串中的所有不同的palindromes $ \ theta（n \ log | \ sigma |）$，并在时间$ \ theta（n | \ sigma |）$ avered Alphabet上的时间$ \ theta（n | \ sigma |） 。使用类似字典的数据结构的减少，我们证明了基于比较的计算模型中该算法的最佳性。
We exhibit an online algorithm finding all distinct palindromes inside a given string in time $\Theta(n\log|\Sigma|)$ over an ordered alphabet and in time $\Theta(n|\Sigma|)$ over an unordered alphabet. Using a reduction from a dictionary-like data structure, we prove the optimality of this algorithm in the comparison-based computation model.