k-Abelian Pattern Matching

to full text (712 kB)   ZIP
involved person(s) / institution(s)author :
datePublished :
  • March 2014
size23 S.

Two words are called \(k\)-abelian equivalent, if they share the same multiplicities for all factors of length at most \(k\). We present an optimal linear time algorithm for identifying all occurrences of factors in a text that are \(k\)-abelian equivalent to some pattern. Moreover, an optimal algorithm for finding the largest \(k\) for which two words are \(k\)-abelian equivalent is given. Solutions for various online versions of the \(k\)-abelian pattern matching problem are also proposed.
Static URLhttps://www.uni-kiel.de/journals/receive/jportal_jparticle_00000021
IDNumber of report :
  • TR_1402