Golnaz Badkobeh
Title: Closed Words: Algorithms and Combinatorics
Abstract: A closed word, also referred to as 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 show that a word of length n contains at least n+1 distinct closed factors. We also characterise words containing exactly n+1 closed factors. Furthermore, we show that a word of length n can contain ?(n^2) many distinct closed factors.
On the algorithmic side, we consider factorising a word into its longest closed factors and present a linear time algorithm for this problem. In addition, we construct a closed factor array, which holds for every position in the word, the longest closed factor starting at that position. We describe our technique that runs in O(n log n/ log log n) time.