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

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

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review


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 - 1 Jan 2019
Event23rd Prague Stringology Conference, PSC 2019 - Prague, Czech Republic
Duration: 26 Aug 201928 Aug 2019

Publication series

NameProceedings of the Prague Stringology Conference, PSC 2019


Conference23rd Prague Stringology Conference, PSC 2019
Country/TerritoryCzech Republic


  • Abelian equivalence
  • Pattern matching
  • Suffix arrays
  • Suffix trees


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

Cite this