Prague Stringology Conference 2019
Golnaz Badkobeh, Hideo Bannai, Maxime Crochemore, Tomohiro I, Shunsuke Inenaga and Shiho Sugimoto
k-Abelian Pattern Matching: Revisited, Corrected, and Extended
| Abstract: |
| 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. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |