TY - GEN

T1 - K-abelian pattern matching

T2 - 23rd Prague Stringology Conference, PSC 2019

AU - Badkobeh, Golnaz

AU - Bannai, Hideo

AU - Crochemore, Maxime

AU - Tomohiro, I.

AU - Inenaga, Shunsuke

AU - Sugimoto, Shiho

N1 - Funding Information:
⋆ Supported by JSPS KAKENHI Grant Number JP16H02783 ⋆⋆ Supported by JSPS KAKENHI Grant Number JP19K20213 ⋆⋆⋆ Supported by JSPS KAKENHI Grant Number JP17H01697
Publisher Copyright:
© Proceedings of the Prague Stringology Conference, PSC 2019. All rights reserved.

PY - 2019

Y1 - 2019

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.

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

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

M3 - Conference contribution

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 -