k-Abelian pattern matching: Revisited, corrected, and extended
Badkobeh, Golnaz; Bannai, Hideo; Crochemore, Maxime; I, Tomohiro; Inenaga, shunsuke and Sugimoto, Shiho. 2019. k-Abelian pattern matching: Revisited, corrected, and extended. pp. 29-40. [Article]
No full text available
Text
K-abelian.pdf - Accepted Version Permissions: Administrator Access Only Download (121kB) |
Abstract or Description
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.
Item Type: |
Article |
||||||
Departments, Centres and Research Units: |
|||||||
Dates: |
|
||||||
Event Location: |
Prague, Czech Republic |
||||||
Date range: |
26 – 28 August 2019 |
||||||
Item ID: |
29104 |
||||||
Date Deposited: |
30 Jul 2020 13:45 |
||||||
Last Modified: |
11 Jun 2021 06:59 |
||||||
URI: |
View statistics for this item...
Edit Record (login required) |