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|).
Fici, G., Lecroq, T., Lefebvre, A., Prieur-Gaston, É. (2015). Online Computation of Abelian Runs. In A.H. Adrian-Horia Dediu, E. Formenti, C.M. Vide, B. Truthe (a cura di), Language and Automata Theory and Applications. LATA 2015 (pp. 391-401). Springer Verlag [10.1007/978-3-319-15579-1_30].
Online Computation of Abelian Runs
FICI, Gabriele;
2015-01-01
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|).
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
Online Computation of Abelian Runs.pdf
Solo gestori archvio
Tipologia:
Versione Editoriale
Dimensione
876.9 kB
Formato
Adobe PDF
|
876.9 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
