A closed word (a.k.a. periodic-like word or complete first return) is a word whose longest border does not have internal occurrences, or, equivalently, whose longest repeated prefix is not right special. We inves- tigate the structure of closed factors of words. We show that a word of length n contains at least n + 1 distinct closed factors, and characterize those words having exactly n + 1 closed factors. Furthermore, we show that a word of length n can contain Θ(n2) many distinct closed factors.
On the Number of Closed Factors in a Word
Liptak, Zsuzsanna
2015-01-01
Abstract
A closed word (a.k.a. periodic-like word or complete first return) is a word whose longest border does not have internal occurrences, or, equivalently, whose longest repeated prefix is not right special. We inves- tigate the structure of closed factors of words. We show that a word of length n contains at least n + 1 distinct closed factors, and characterize those words having exactly n + 1 closed factors. Furthermore, we show that a word of length n can contain Θ(n2) many distinct closed factors.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
978-3-319-15579-1_29.pdf
solo utenti autorizzati
Tipologia:
Versione dell'editore
Licenza:
Copyright dell'editore
Dimensione
183.39 kB
Formato
Adobe PDF
|
183.39 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.
