# Clarification of leftmost maximal periodicities

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.

• Can you please clarify why this question is important to you? Enumeration of all occurrences certainly doesn’t care which one is leftmost. May 28, 2018 at 10:41
• @DmitriUrbanowicz Because it's important to know what an algorithm is, or is not, computing. I also gave a specific example which shows the importance. I also do not understand how Kolpakov & Kucherov achieve their result unless Main's algorithm computes 'maximal periodicities that are leftmost' - which it seems is not the case. May 28, 2018 at 10:50
• Yes, the example shows the difference. But it doesn’t explain what’s behind your “as best as I can tell”. Where exactly (as you think) result of Kolpakov and Kucherov would fail due to this difference? May 28, 2018 at 15:54

1. It may report some nonmaximal periodicity, which is suffix of $t_h u_h$ and still can be extended to the right.
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.