<p>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,</p>

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

<p>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.</p>

<p>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.)</p>

CC BY-SA 4.0
2018-05-31T16:38:11.440Z
2018-06-01T06:11:25.613Z
2018-06-01T06:11:25.613Z
Dmitri Urbanowicz
<p><a href="https://www.sciencedirect.com/science/article/pii/0166218X89900516" rel="nofollow noreferrer">Main</a> describes an algorithm for detecting all 'leftmost maximal' periodicities in a string in linear time, using the following definitions:</p>

<ul>
<li>A <em>periodicity</em> of a string $x$ a nonempty substring of $x$ of the form $p^mq$ with $m\ge2$ and $q$ a proper prefix of $p$.</li>
<li>A <em>leftmost</em> 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$.</li>
<li>A periodicity $x[i] \dots x[j]$ with period $k$ is <em>maximal</em> if:

<ol>
<li>$i = 1$ or $x[i - 1] \dots x[j]$ is not a periodicity with period $k$, and</li>
<li>$j = |x|$ or $x[i] \dots x[j + 1]$ is not a periodicity with period $k$</li>
</ol></li>
</ul>

<p>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$.</p>

<p>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$.</p>

<p>My question concerns the meaning of "leftmost maximal", particularly if this should be read "periodicities that are both leftmost <strong>and</strong> 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.</p>

<p>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$).</p>

<p>However, as best as I can tell, the result of <a href="http://monge.univ-mlv.fr/~koutcher/PAPERS/KolpakovKucherovFOCS99.pdf" rel="nofollow noreferrer">Kolpakov and Kucherov</a>, 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.</p>

CC BY-SA 4.0
2018-05-28T10:41:30.170Z
Can you please clarify why this question is important to you? Enumeration of all occurrences certainly doesn’t care which one is leftmost.
Dmitri Urbanowicz
CC BY-SA 4.0
2018-05-28T10:50:48.643Z
@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.
Daniel
CC BY-SA 4.0
2018-05-28T15:54:23.987Z
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?
Dmitri Urbanowicz
<string-search>
Clarification of leftmost maximal periodicities
Daniel
# Clarification of leftmost maximal periodicities

(Asked by: username_0 on 2018-05-26)

[Main](https://www.sciencedirect.com/science/article/pii/0166218X89900516) 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](http://monge.univ-mlv.fr/~koutcher/PAPERS/KolpakovKucherovFOCS99.pdf), 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.

**Tags:** string-search
> **Comments:**
> **username_1**: Can you please clarify why this question is important to you? Enumeration of all occurrences certainly doesn’t care which one is leftmost.  
> **username_0**: @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.  
> **username_1**: 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?  

---

## 1 answers

### Answer by username_1 on 2018-05-31. Score: 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.)


---

