@inbook{212c5601fbe6461284f767d15809966e,

title = "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.",

keywords = "Abelian equivalence, Pattern matching, Suffix arrays, Suffix trees",

author = "Golnaz Badkobeh and Hideo Bannai and Maxime Crochemore and Tomohiro I and Shunsuke Inenaga and Shiho Sugimoto",

year = "2019",

month = jan,

day = "1",

language = "English",

series = "Proceedings of the Prague Stringology Conference, PSC 2019",

publisher = "Prague Stringology Club",

pages = "29--40",

editor = "Jan Holub and Jan Zdarek",

booktitle = "Proceedings of the Prague Stringology Conference, PSC 2019",

note = "23rd Prague Stringology Conference, PSC 2019 ; Conference date: 26-08-2019 Through 28-08-2019",

}