On the Number of Closed Factors in a Word

Gabriele Fici, Golnaz Badkobeh, Zsuzsanna Lipták

Risultato della ricerca: Other

6 Citazioni (Scopus)

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 investigate 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.
Lingua originaleEnglish
Pagine381-390
Numero di pagine10
Stato di pubblicazionePublished - 2015

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cita questo

Fici, G., Badkobeh, G., & Lipták, Z. (2015). On the Number of Closed Factors in a Word. 381-390.