The computational model we use to design and analyze our algorithms is the standard unit-cost RAM with logarithmic word size, which is generally used in the analysis of algorithms.
In the upcoming algorithmic problems, we assume that the words we process are sequences of integers. In general, if the input word has length \(n\)  then we assume its letters are in \(\lbrace 1,\ldots ,n\rbrace \) , so each letter fits in a single memory-word. This is a common assumption in stringology (see, e.g., the discussion in [1]}).
For a word \(w\) , \(|w|=n\) , we build in \({\mathcal {O}}(n)\)  time the suffix array as well as data structures allowing us to retrieve in constant time the length of the longest common prefix of any two suffixes \(w[i,n]\)  and \(w[j,n]\) 
of \(w\) , denoted \({\mathit {LCP}}_w(i,j)\)  (the subscript \(w\)  is omitted when there is no danger of confusion). Such structures are called \({\mathit {LCP}}\)  data structures in the following (see, e.g., [1]}, [3]}). We begin with a simple lemma.

Given a word \(w\) , \(|w|=n\) , we can process it in \({\mathcal {O}}(n)\)  time such that, for each \(i,p\le n\) , we can return in \({\mathcal {O}}(1)\)  time the longest factor of period \(p\)  starting at position \(i\)  in \(w\) .
