Autor: |
Crochemore, Maxime, Iliopoulos, Costas, Kociumaka, Tomasz, Kubica, Marcin, Pachocki, Jakub, Radoszewski, Jakub, Rytter, Wojciech, Tyczyński, Wojciech, Waleń, Tomasz |
Rok vydání: |
2012 |
Předmět: |
|
Druh dokumentu: |
Working Paper |
Popis: |
We derive a simple efficient algorithm for Abelian periods knowing all Abelian squares in a string. An efficient algorithm for the latter problem was given by Cummings and Smyth in 1997. By the way we show an alternative algorithm for Abelian squares. We also obtain a linear time algorithm finding all `long' Abelian periods. The aim of the paper is a (new) reduction of the problem of all Abelian periods to that of (already solved) all Abelian squares which provides new insight into both connected problems. |
Databáze: |
arXiv |
Externí odkaz: |
|