Online Computation of Abelian Runs
- Autori: Fici, G.; Lecroq, T.; Lefebvre, A.; Prieur-Gaston, É.
- Anno di pubblicazione: 2015
- Tipologia: Contributo in atti di convegno pubblicato in volume
- OA Link: http://hdl.handle.net/10447/153515
Abstract
Given a word w and a Parikh vector P, an abelian run of period P in w is a maximal occurrence of a substring of w having abelian period P. We give an algorithm that finds all the abelian runs of period P in a word of length n in time O(n × |P|) and space O(σ + |P|).