K-abelian pattern matching: Revisited, corrected, and extended

Golnaz Badkobeh, Hideo Bannai, Maxime Crochemore, I. Tomohiro, Shunsuke Inenaga, Shiho Sugimoto

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference, PSC 2019
EditorsJan Holub, Jan Zdarek
PublisherPrague Stringology Club
Number of pages12
ISBN (Electronic)9788001066188
Publication statusPublished - 2019
Event23rd Prague Stringology Conference, PSC 2019 - Prague, Czech Republic
Duration: Aug 26 2019Aug 28 2019

Publication series

NameProceedings of the Prague Stringology Conference, PSC 2019


Conference23rd Prague Stringology Conference, PSC 2019
Country/TerritoryCzech Republic

All Science Journal Classification (ASJC) codes

  • Mathematics(all)


Dive into the research topics of 'K-abelian pattern matching: Revisited, corrected, and extended'. Together they form a unique fingerprint.

Cite this