Clarification of leftmost maximal periodicities

Question

Main describes an algorithm for detecting all 'leftmost maximal' periodicities in a string in linear time, using the following definitions:

• A periodicity of a string $x$ a nonempty substring of $x$ of the form $p^mq$ with $m\ge2$ and $q$ a proper prefix of $p$.
• A leftmost periodicity of $x$ is a periodicity $x[i] \dots x[j]$ such that if $x[i] \dots x[j] = x[i'] \dots x[j']$ then $i \le j$.
• A periodicity $x[i] \dots x[j]$ with period $k$ is maximal if:
  1. $i = 1$ or $x[i - 1] \dots x[j]$ is not a periodicity with period $k$, and
  2. $j = |x|$ or $x[i] \dots x[j + 1]$ is not a periodicity with period $k$

Main goes on to present a theorem (3.4): given an s-factorisation of a string $x=u_1 \dots u_k$ and let $r$ be a periodicity of $x$, with leftmost occurrence of $r$ at $x[i] \dots x[j]$, and with the $j^{th}$ position of $x$ within $u_h$, then the $i^{th}$ position of $x$ occurs before $u_h$.

This theorem forms the basis of the algorithm for computing 'leftmost maximal' periodicities of a given string $x$. The algorithm finds all maximal periodicities of $t_hu_h$ for $2 \le h \le k$ where $t_h$ is a substring of length $2|u_{h-1}| + |u_h|$ that immediately precedes $u_h$, such that each periodicity begins in $t_h$ and ends in $u_h$.

My question concerns the meaning of "leftmost maximal", particularly if this should be read "periodicities that are both leftmost and maximal", or "maximal periodicities that are leftmost". To clarify the distinction, consider the string $x=aaabcaabd$. Clearly the periodicity $aaa$ starting at $x[1]$ is leftmost maximal under both interpretations, but is the periodicity $aa$ starting at $x[6]$ also leftmost maximal? According the the first interpretation, it isn't, and $x$ only has one leftmost maximal periodicity. According to the second, it is, and $x$ has two leftmost maximal periodicities.

It seems to me that Main's algorithm gives 'leftmost maximal' periodicities of the first kind: the s-factorisation of $aaabcaabd$ is $a|aa|b|c|aab|d$, hence the second $aa$ periodicity starting at $x[6]$ will not be included as it is contained entirely in a single s-factor ($u_5 = aab$).

However, as best as I can tell, the result of Kolpakov and Kucherov, for computing all maximal periodicities of string in linear time, assumes the second definition. Kolpakov and Kucherov use Main's result as a key component of their algorithm.

Answer 1

Main explicitly states that his algorithm may output some nonleftmost or nonmaximal occurrences of periodicities. Indeed, theorem 3.4 only guarantees that every leftmost maximal periodicity will be reported at least once and that total size of the output is linear in size of input string. Namely,

1. It may report some nonmaximal periodicity, which is suffix of $t_h u_h$ and still can be extended to the right.
2. There might be several occurrences of the same substring such that none of them fit into a single s-factor.

Kolpakov and Kucherov slightly modify Main's algorithm to exclude suffixes of $t_h u_h$ but allow either $t_h$ or $u_h$ to be empty. This way the algorithm never reports nonmaximal periodicities and at the same time finds every occurrence of maximal periodicity that either spans several s-factors or touches their boundaries.

So, Kolpakov and Kucherov don't rely on the notion of leftmost occurrences at all. They only need to find every periodicity that is not strictly inside single factor of s-factorization. (And prove that there will be only linear number of occurrences in total, of course.)