Computing Abelian covers and Abelian runs

Shohei Matsuda, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda

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

5 Citations (Scopus)


Two strings u and v are said to be Abelian equivalent if u is a permutation of the characters of v. We introduce two new regularities on strings w.r.t. Abelian equivalence, called Abelian covers and Abelian runs, which are generalizations of covers and runs of strings, respectively. We show how to determine in O(n) time whether or not a given string w of length n has an Abelian cover. Also, we show how to compute an O(n2)-size representation of (possibly exponentially many) Abelian covers of w in O(n2) time. Moreover, we present how to compute all Abelian runs in w in O(n2) time, and state that the maximum number of all Abelian runs in a string of length n is Ω(n2).

Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2014, PSC 2014
EditorsJan Holub, Jan Zd'arek
PublisherPrague Stringology Club
Number of pages9
ISBN (Electronic)9788001055472
Publication statusPublished - 2014
Event18th Prague Stringology Conference, PSC 2014 - Prague, Czech Republic
Duration: Sept 1 2014Sept 3 2014

Publication series

NameProceedings of the Prague Stringology Conference 2014, PSC 2014


Other18th Prague Stringology Conference, PSC 2014
Country/TerritoryCzech Republic

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'Computing Abelian covers and Abelian runs'. Together they form a unique fingerprint.

Cite this