k-Abelian Pattern Matching: Revisited, Corrected, and Extended
k-Abelian Pattern Matching: Revisited, Corrected, and Extended
复制标题
DOI：
--
复制
发表时间：
2019-08
期刊：
影响因子：
1.1
通讯作者：
Golnaz Badkobeh;H. Bannai;M. Crochemore;⋆⋆ TomohiroI4;Shunsuke Inenaga;Shiho Sugimoto
中科院分区：
文献类型：
--
作者：
Golnaz Badkobeh;H. Bannai;M. Crochemore;⋆⋆ TomohiroI4;Shunsuke Inenaga;Shiho Sugimoto
如果两个长度相等的字符串共享最多k个长度的相同多因子集，则称为k-阿贝尔等价。Ehlers等人[JDA， 2015]考虑了k-阿贝尔模式匹配问题，其任务是找到文本T中与模式p具有k-阿贝尔等价的所有因子。他们声称了k-阿贝尔模式匹配问题的离线和在线版本的许多算法结果。在本文中，我们首先论证了Ehlers等人[JDA， 2015]声称的一些结果包含重大错误，然后我们提出了一种新的算法，在O（n+m）时间和O(m)空间内，在O（n+m）时间和O(m)空间内正确解决问题的离线版本，其中n = |T|和m = |P|。我们还展示了如何纠正他们的在线算法中的错误，以及他们的实时算法中的错误，以解决一个稍微不同的问题，称为扩展k-Abelian模式匹配问题。
Two strings of equal length are called k-Abelian equivalent, if they share the same multi-set of factors of length at most k. Ehlers et al. [JDA, 2015] considered the k-Abelian pattern matching problem, where the task is to find all factors in a text T that are k-Abelian equivalent to a pattern P. They claimed a number of algorithmic results for the off-line and on-line versions of the k-Abelian pattern matching problem. In this paper, we first argue that some of the claimed results by Ehlers et al. [JDA, 2015] contain major errors, and then we present a new algorithm that correctly solves the offline version of the problem within the same bounds claimed by Ehlers et al., in O(n+m) time and O(m) space, where n = |T| and m = |P|. We also show how to correct errors in their online algorithm, and errors in their real-time algorithms for a slightly different problem called the extended k-Abelian pattern matching problem.