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

TY - CHAP

T1 - K-abelian pattern matching

T2 - 23rd Prague Stringology Conference, PSC 2019

AU - Badkobeh, Golnaz

AU - Bannai, Hideo

AU - Crochemore, Maxime

AU - I, Tomohiro

AU - Inenaga, Shunsuke

AU - Sugimoto, Shiho

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Abelian equivalence

KW - Pattern matching

KW - Suffix arrays

KW - Suffix trees

UR - http://www.scopus.com/inward/record.url?scp=85086064946&partnerID=8YFLogxK

M3 - Conference paper

AN - SCOPUS:85086064946

T3 - Proceedings of the Prague Stringology Conference, PSC 2019

SP - 29

EP - 40

BT - Proceedings of the Prague Stringology Conference, PSC 2019

A2 - Holub, Jan

A2 - Zdarek, Jan

PB - Prague Stringology Club

Y2 - 26 August 2019 through 28 August 2019

ER -