Skip to main content
Passa alla visualizzazione normale.


Pari opportunità

GABRIELE FICI

Online Computation of Abelian Runs

  • Authors: Fici, G.; Lecroq, T.; Lefebvre, A.; Prieur-Gaston, É.
  • Publication year: 2015
  • Type: 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|).