$S[s_{i}+|w|+Ex_{r}]$ is within the periodic run containing $w_{0}$. It
follows that $S[s_{i}+|w|+Ex_{r}]=S[s_{0}+p\cdot
i+|w|+Ex_{r}]=S[s_{0}+|w|+Ex_{r}]$. Both of the symbols that decide the
lexicographic order between $S^{s}$ and $S^{s_{i}}$ are independent from $i$.
Therefore, Either $[0\ldots i^{\prime})\subseteq I_{>}$ or $[0\ldots
i^{\prime}]\cup I_{>}=\varnothing$. ∎

######  Claim 68.

The interval $(i^{\prime}\ldots|C|-1]$ is either fully contained in $I_{>}$ or
disjoint from $I_{>}$.

For $i\in(i^{\prime}\ldots|C|-1]$ we have $Ex_{r}>Ex^{C}_{r}-p\cdot i$ and
therefore $r_{i}=Ex^{C}_{r}-p\cdot i+|w|$. Therefore, the lexicographical
order between $S^{s}$ and $S^{s_{i}}$ is decided by the values of
$c^{i}_{1}=S[s+|w|+Ex^{C}_{r}-p\cdot i]$ and
$c^{i}_{2}=S[s_{i}+|w|+Ex^{C}_{r}-p\cdot i]$. For $i>i^{\prime}$,
$s+|w|+Ex^{C}_{r}-p\cdot i<s+|w|+Ex^{C}_{r}$. Therefore, the index
$s+|w|+Ex^{C}_{r}-p\cdot i$ is contained within the run with period $p$
containing $w$. It follows that $c^{i}_{1}=S[s+|w|+Ex^{C}_{r}-p\cdot i]$ is
independent of $i$. Note that $c^{i}_{2}=S[s_{0}+p\cdot
i+|w|+Ex^{C}_{r}-p\cdot i]=S[s_{0}+|w|+Ex^{C}_{r}]$. Both of the symbols that
decide the lexicographic order between $S^{s}$ and $S^{s_{i}}$ are independent
from $i$. Therefore, Either $(i^{\prime}\ldots|C|-1]\subseteq I_{>}$ or
$(i^{\prime}\ldots|C|-1]\cup I_{>}=\varnothing$. ∎

We use a single $LCP$ query to find $r_{0}$. If $r_{0}<|w|$, we can either
report $I_{<}=[0\ldots|C|-1]$ or $I_{<}=\varnothing$ according to the
lexicographical order between $S^{s}$ and $S^{s_{0}}$.

If $r_{0}\geq|w|$, we employ Lemma 36 to find $Ex^{C}_{r}$ and $Ex_{r}$ in
$O(\log(n))$ time. With these in hand, $i^{\prime}$ can be evaluated in
constant time. We lexicographically compare between $S^{s}$ and a single
suffix from each of the intervals $[0\ldots i^{\prime})$,
$(i^{\prime}\ldots|C|-1]$. According to Claim 67 and Claim 68, the results of
these comparisons can be used to decide if $[0\ldots i^{\prime})$ and
$(i^{\prime}\ldots|C|-1]$ form a part of $I_{>}$.

If $i^{\prime}$ is an integer, the single suffix $S^{s_{i^{\prime}}}$ needs to
be compared to $S^{s}$ in order to decide if $i^{\prime}\in I_{>}$. We can
evaluate $i^{\prime}$ in constant time. We report $I_{>}$ to be the union of
the intervals that were found to be contained in $I_{>}$ and possibly
$i^{\prime}$.

In the process of evaluating $I_{>}$ we executed a constant number of
arithmetic operations and $lcp$ queries, as well as a single application of
Lemma 36. The time complexity is bounded by $O(\log(n))$. ∎

####  6.2.1 Proof of Theorem 63

See 63 The following well known fact is helpful for proving Theorem 63, and is
derived directly from the periodicity lemma.

######  Fact 69.

Two runs $r_{1}$ and $r_{2}$ in a string $S$ can have an overlap with length
at most $per(r_{1})+per(r_{2})-1$

To prove Theorem 63, we prove the following lemma:

######  Lemma 70.

For every $k\in[1\ldots\log_{\frac{3}{2}}(n)]$, there can be at most two
distinct runs $R$ containing the index $x$ with $(\frac{3}{2})^{k-1}\leq
Per(R)<(\frac{3}{2})^{k}$.

Proof: Assume to the contrary that there are three distinct runs
$R_{1}=S[s_{1}\ldots e_{1}]$, $R_{2}=[s_{2}\ldots e_{2}]$ and
$R_{3}=S[s_{3}\ldots e_{3}]$ containing the index $x$ with $per(R_{i})=p_{i}$
and $(\frac{3}{2})^{k-1}\leq p_{i}<(\frac{3}{2})^{k}$ for $i\in\\{1,2,3\\}$.
Assume w.l.o.g that $s_{1}\leq s_{2}\leq s_{3}$. If one of the runs in our
settings, $R_{i}$, fully contains one of the other runs, $R_{j}$. The overlap
between them is $|R_{j}|\geq 5\cdot p_{j}>p_{j}+\frac{3}{2}\cdot
p_{j}>p_{j}+p_{i}$, in contradiction to Fact 69. Therefore, no run is
containing the other and it must be the case that $e_{1}<e_{2}<e_{3}$. It
follows that $R_{2}$ is completely covered by $R_{1}$ and $R_{3}$ and
therefore $|R_{2}|\leq|R_{1}\cap R_{2}|+|R_{2}\cap R_{3}|$. Due to Fact 69,
$|R_{2}\cap R_{1}|<p_{2}+p_{3}$ and $|R_{2}\cap R_{3}|<p_{2}+p_{3}$. Summing
the two yields $|R_{1}\cap R_{2}|+|R_{2}\cap R_{3}|<2\cdot p_{2}+p_{1}+p_{3}$
and from transitivity we get $|R_{2}|<2\cdot p_{2}+p_{1}+p_{3}$. Since $5\cdot
p_{2}\leq|R_{2}|$, we have $3\cdot p_{2}<p_{1}+p_{3}$. Let $p_{m}$ be the
maximal period among $p_{1}$ and $p_{3}$. We must have $3\cdot p_{2}<2\cdot
p_{m}$ which finally yields $\frac{3}{2}\cdot p_{2}<p_{m}$, which is a
contradiction to the assumption that
$p_{m},p_{2}\in[(\frac{3}{2})^{k-1}\ldots(\frac{3}{2})^{k}-1]$ ∎

With Lemma 70, the proof of Theorem 63 is straightforward. For every
$k\in[1\ldots\log_{\frac{3}{2}}(n)]$, there are at most 2 runs with period
$(\frac{3}{2})^{k-1}\leq Per(R)<(\frac{3}{2})^{k}$ containing $x$. ∎

###  6.3 Proof of Lemma 41

See 41

Proof: We start by proving the following claim

######  Claim 71.

Let $U=u_{0},u_{1}\ldots u_{|U|-1}$ be a sequence of interval increment
updates with $u_{t}=(i_{t},j_{t},1)$ and let $p$ be an integer. If
$\\{i_{t}\\}$ and $\\{j_{t}\\}$ are both $p$-normal sequences with
$deg(\\{i_{t}\\})=d_{i}$ and $deg(\\{j_{t}\\})=d_{j}$, Applying all the
interval updates in $U$ to an array can be reduced to applying
$O(2^{d_{i}+d_{j}})$ interval increment updates and stairs updates with stair
width $|p|$. These stairs updates can be obtained in time $O(2^{d_{i}+d_{j}})$
given the representation of $\\{i_{t}\\}$ and $\\{j_{t}\\}$ as $p$-normal
sequences.

Poof: By strong induction on $d_{i}+d_{j}$. Our base case is when
$d_{i}=d_{j}=1$. If it is the case, one of the following must occur:

  1. 1.

Both $i_{t}$ and $j_{t}$ are arithmetic progressions with difference $p$.

  2. 2.

One of $i_{t}$,$j_{t}$ is an arithmetic progression with difference $p$ and
the other is fixed.

  3. 3.

Both $i_{t}$ and $j_{t}$ are fixed.

Lemma 106 in Section 8 suggests that applying all the interval updates
$(i_{t},j_{t},1)$ for $t\in[0\ldots|U|-1]$ can be reduced to applying a
constant number of stairs updates. This concludes the induction base.

Assume $d_{i}+d_{j}=D>2$. In particular, assume $d_{i}\geq 2$. The case in
which $d_{j}\geq 2$ is treated symmetrically. We start with the following
claim:

######  Claim 72.

If $d_{i}\geq 2$, $CT(\\{i_{t}\\})$ contains a $p$-normal sequence
$B^{\prime}$ with $deg(B^{\prime})=2$.

Proof: It is easy to observe that a node corresponding to a $p$-normal
sequence $B^{\prime}$ has $deg(B^{\prime})=2$ iff its construction tree is a
root with two leaf children. Every finite full binary tree of size at least
$3$ must contain a node with two leaf children ∎

Let $B^{\prime}$ be a $p$-normal sequence in $CT(\\{i_{t}\\})$ with
$deg(B^{\prime})=2$. Assume that $B^{\prime}$ is a maximum sequence
$b^{\prime}_{t}=max(a^{1}_{t},a^{2}_{t})$. The case in which $B^{\prime}$ is a
minimum sequence can be handled Similarly. $a^{1}_{t}$ and $a^{2}_{t}$ are
both $p$-normal sequences with degree $1$. So one of the following must occur:

  1. 1.

Both $a^{1}_{t}$ and $a^{2}_{t}$ are fixed

  2. 2.

Both $a^{1}_{t}$ and $a^{2}_{t}$ are arithmetic progression with difference
$p$.

  3. 3.

One of $a^{1}_{t}$, $a^{2}_{t}$ is an arithmetic progression with difference
$p$, and the other is fixed.

If (1) occurs, $B^{\prime}$ can be replaced with the fixed value
$max(a^{1}_{0},a^{2}_{0})$. If (2) occurs, $B^{\prime}$ can be replaced with
the arithmetic progression $a^{y}_{0}+p\cdot t$ with the maximal value of
$a^{y}_{0}$ for $y\in\\{0,1\\}$. In both (1) and (2), we replace every
occurrence of $B^{\prime}$ in $\\{i_{t}\\}$ with a $p$-normal sequence with
degree $1$. By doing so we obtain an equivalent sequence $\\{i^{*}_{t}\\}$
with degree $d^{*}_{i}<d_{i}$. From the induction hypothesis, the updates
sequence $\\{(i^{*}_{t},j_{t},1)\\}$ can be reduced to
$O(2^{d^{*}_{i}+d_{j}})=O(2^{d_{i}+d_{j}})$ stairs updates. Since
$\\{i^{*}_{t}\\}$ is equivalent to $\\{i_{t}\\}$, applying these stairs
updates is equivalent to applying the updates of $U$.

If (3) occurs, assume w.l.o.g that $a^{1}_{t}$ is a fixed value sequence with
value $a$ and $a^{2}_{t}=a^{2}_{0}+p\cdot t$. Assume that $p\geq 0$ and let
$t^{\prime}=\lfloor\frac{a-a^{2}_{0}}{p}\rfloor$. It can be easily verified
that $max(a^{1}_{t},a^{2}_{t})=a^{1}_{t}=a$ for $t\in[0\ldots t^{\prime}]$ and
that $max(a^{1}_{t},a^{2}_{t})=a^{2}_{t}=a^{2}_{0}+p\cdot t$ for
$t\in[t^{\prime}+1\ldots|U|-1]$.

Therefore, in $t\in[0\ldots t^{\prime}]$ we can replace every occurrence of
$B^{\prime}$ with a fixed sequence $a$. In $t\in[t^{\prime}+1\ldots|U|-1]$ we
can replace every occurrence of $B^{\prime}$ with an arithmetic progression
$a^{2}_{0}+p$. In both cases, we replace an expression with degree $2$ with an
expression with degree $1$ and therefore obtain a $p$-normal sequence with a
strictly lower degree. By the recursion hypothesis, both the updates
$u_{0},u_{1}\ldots u_{t^{\prime}}$ and the updates $u_{t^{\prime}+1}\ldots
u_{|U|-1}$ can be represented by a set of $O(2^{d_{i}+d_{j}-1})$ stairs
updates. Applying both of these sets is equivalent to applying all the updates
in $U$. The collective size of these sets is $O(2\cdot
2^{d_{i}+d_{j}-1})=O(2^{d_{i}+d_{j}})$.

An algorithm for finding the set of stairs updates in $O(2^{d_{i}+d_{j}})$
time (ignoring polynomial factors) can be directly derived from the proof ∎

With Claim 71, we are finally ready to prove Lemma 41.

Let $d_{i}=Deg(\\{i_{t}\\})$ and $d_{j}=Deg(\\{i_{t}\\})$. According to Lemma
71, the updates of $U$ can be reduced to $O(2^{d_{i}+d_{j}})$ stairs or
interval updates in $O(2^{d_{i}+d_{j}})$ time. Since $d_{i},d_{j}\in O(1)$, we
have $O(2^{d_{i}+d_{j}})=O(1)$. ∎

##  7 Extension Restricting Selection Queries

This section is dedicated to proving Theorem 23.

###  7.1 Occurrence Selection Queries

We start by providing data structure for the following problem:

Occurrence Selection Query
Input: $POR_{w}$ the periodic occurrences representation of a word $w$. Query:
upon input $i$. Return $A_{w}[i]$

The goal is to efficiently process $POR_{w}$ to enable an occurrence selection
query in polylogarithmic time, without explicitly constructing $A_{w}$.
Specifically, we wish to construct a data structure for OS queries in time
$\tilde{\mathcal{O}}(|POR_{w}|)$.

In this section, we make an extensive use of the terms period rank, tail of a
cluster, and head of a cluster as defined in Section 4. We provide the
following example to better familiarize the reader with these terms. Figure 1
is another example of these terms.

######  Example 73.

Let $S=BAABBABBABBABBABBABAB$. The cluster $C=(4,13,3)$ represents a periodic
set of occurrence of $w=BBABBAB$ with period $3$. Consider the occurrence in
$w_{0}=S[4\ldots 10]$. Its period rank is $r_{p}(w_{0})=3$, since there are 3
consecutive occurrences of $w[5\ldots 7]=BAB$ following index $10$. The period
rank of the second occurrence in the cluster, $w_{1}=S[7\ldots 13]$, is
$r_{p}(w_{1})=2$. One can easily observe that the $t$’th occurrence has
$r_{p}(w_{t})=|C|-t-1$. The tail of $C$ is $Tail(C)=S[20\ldots 21]=AB$ and the
head is $Head(C)=S[1\ldots 3]=BAA$.

The tail of a cluster can be equivalently described as the suffix following
the rightmost consecutive occurrence of $w_{s}$ following $w_{0}$ (or
equivalently, any other $w_{t}$). Since $w_{|C|-1}$ has the rightmost
occurrence of $w_{s}$ as a suffix, the tail starts right after $w_{|C|-1}$.
Notice that we must have $Tail(C)[1\ldots p]\neq w_{s}$. Otherwise, there
would be another occurrence of $w$ exactly $p$ indexes to the right of
$w_{|C|-1}$.

######  Lemma 74.

Let $C^{i}=(a^{i},b^{i},p),C^{d}=(a^{d},b^{d},p)\in POR_{w}$ be an increasing
cluster and a decreasing cluster respectively (as defined in Section 4). Let
$w_{1}=S[s_{1}\ldots e_{1}]$ be an occurrence of $w$ implied by $C^{i}$ and
$w_{2}=[s_{2}\ldots e_{2}]$ be an occurrence of $w$ implied by $C^{d}$. It
must be the case that $S[s_{1}\ldots n]>_{L}S[s_{2}\ldots n]$.

Proof: In what follows, we slightly abuse the notation of $<_{L}$. We use the
notation $w_{1}<_{L}w_{2}$ between two equal words to denote that the suffixes
starting in their corresponding starting indexes have $S[s_{1}\ldots
n]<_{L}S[s_{2}\ldots n]$.

We distinguish between three cases (See Figure 7 for a visualization):

  1. 1.

$r_{p}(w_{1})>r_{p}(w_{2})$: In this case, the first $|w|+p\cdot r_{p}(w_{2})$
symbols of both suffixes match. The $p$ symbols following $S[e_{1}+p\cdot
r_{p}(w_{1})]$ are an occurrence of $w_{s}$. The $p$ symbols following
$S[e_{2}+p\cdot r_{p}(w_{2})]$ are $Tail(C^{d})$. Since $C^{d}$ is decreasing,
$w_{s}>Tail(C^{d})$ and we have $w_{1}>_{L}w_{2}$.

  2. 2.

$r_{p}(w_{1})<r_{p}(w_{2})$: In this case, the first $|w|+p\cdot r_{p}(w_{1})$
symbols of both suffixes match. The $p$ symbols following $S[e_{1}+p\cdot
r_{p}(w_{1})]$ are $Tail(C^{i})$ and the $p$ symbols following $S[e_{2}+p\cdot
r_{p}(w_{2})]$ are an occurrence of $w_{s}$. Since $C^{i}$ is increasing,
$Tail(C^{i})>w_{s}$ and we have $w_{1}>_{L}w_{2}$.

  3. 3.

$r_{p}(w_{1})=r_{p}(w_{2})$ : In this case, the lexicographic order is
determined by the lexicographic order between $Tail(C^{i})$ and $Tail(C^{d})$.
We have $Tail(C^{i})>_{L}w_{s}>_{L}Tail(C^{d})$.

∎

Figure 7: A visualization of the proof of Lemma 74. [Left] A demonstration of
the first case. In the picture, $r_{p}(w_{1})=3$ and $r_{p}(w_{2})=2$.
Following the first two instances of $w_{s}$, the comparison between $w_{1}$
and $w_{2}$ comes down to comparing $w_{s}$ and $Tail(C^{d})$. [Center] A
demonstration of the second case with $r_{p}(w_{1})=2$ and $r_{p}(w_{2})=3$.
Symmetrically to the previous case, the comparison between $w_{1}$ and $w_{2}$
comes down to comparing $Tail(C^{i})$ and $w_{s}$. [Right] A demonstration of
the third case with $r_{p}(w_{1})=r_{p}(w_{2})=3$. The comparison between
$w_{1}$ and $w_{2}$ comes down to the comparison between the tails of the
clusters.

Lemma 74 suggests that $A_{w}$ can be expressed as the concatenation of two
arrays $A=D[1\ldots|D|]I[1\ldots|I|]$ with $D$ the array of lexicographically
sorted suffixes implied by decreasing clusters and $I$ the lexicographically
sorted suffixes implied by increasing clusters. We can use this fact to reduce
our task to either querying $D$ or $I$ for the element in a specified index.
Upon a query for $A_{w}[i]$ with $i\leq|D|$ , we query $D[i]$. For $i>|D|$ we
query $I[i-|D|-1]$. We can calculate the size of $D$ in $O(\frac{n}{k})$ time
by accumulating the sizes of the decreasing clusters. From now on, we show how
to construct a data structure for finding $I[i]$ for a given index $i$. A data
structure for finding $D[i]$ can be constructed in a similar manner.

Using the same arguments as in the proof of Lemma 74, the following can be
proven:

######  Lemma 75.

$C_{1}=(a_{1},b_{1},p),C_{2}=(a_{2},b_{2},p)\in Occ$ be two increasing
clusters (not necessarily distinct). Let $w_{1}=S[s_{1}\ldots e_{1}]$ be an
occurrence of $w$ implied by $C_{1}$ and $w_{2}=[s_{2}\ldots e_{2}]$ be an
occurrence of $w$ implied by $C_{2}$.

  1. 1.

If $r_{p}(w_{1})>r_{p}(w_{2})$, $w_{1}<_{L}w_{2}$.

  2. 2.

If $r_{p}(w_{1})=r_{p}(w_{2})$ and $Tail(C_{1})<_{L}Tail(C_{2})$,
$w_{1}<_{L}w_{2}$.

Lemma 75 suggest that sorting the suffixes of $I$ by lexicographic order is
equivalent to sorting them primarily by decreasing order of their rank, and
secondary by increasing lexicographic order of the tails of their clusters.
Namely, $I$ can be written as the concatenation of $m$ arrays, with $m$ being
the maximal rank of an occurrence within an increasing cluster.
$I=T_{m},T_{m-1}\ldots T_{1},T_{0}$. For every $r\in[0\ldots m]$, $T_{r}$ is
the set of occurrences with rank $r$ sorted by increasing lexicographic order
of the tails of their clusters. The size of $T_{r}$ is the amount of clusters
with size at least $r+1$. Given an index $i$, we are interested in finding $r$
and $i^{\prime}$ such that $I[i]\in T_{r}$ and in particular,
$I[i]=T_{r}[i^{\prime}]$. See Figure 8

Figure 8: A demonstration of the structure of $A_{w}$.

We process the set of increasing clusters in $POR_{w}$, denoted as $POR_{I}$,
to obtain the following.

  1. 1.

$Ranks=r_{1},r_{2},r_{3}\ldots r_{d}$ \- the list of distinct values of the
maximal ranks within an increasing cluster in $POR_{I}$ in decreasing order.
Namely, if there is a cluster $C\in POR_{I}$ with size $x$, the number $x-1$
is in $Ranks$.

  2. 2.

$Sizes=s_{1},s_{2},s_{3}\ldots s_{d}$ \- a list with $s_{q}$ being the amount
of clusters with a maximal rank of at least $r_{q}$. Note that $Sizes$ is
monotonically increasing.

  3. 3.

$Tails=t_{1},t_{2},t_{3}\ldots t_{|POR_{I}|}$ \- a lexicographically sorted
list of the tails of the clusters in $POR_{I}$. $Tail(C)$ is represented in
$Tails$ as a pointer to $C$.

Note that $r_{1}=m$ and $s_{d}=|POR_{I}|$. We define a set of $d$ subarrays
(denoted as ’buckets’) of $I$ such that $I=B_{1},B_{2}\ldots B_{d}$. The
bucket $B_{q}$ for $q\in[1\ldots d-1]$ contains the concatenation of $T_{z}$
for $z\in[r_{q+1}+1\ldots r_{q}]$ in decreasing order of $z$ (as they appear
in $I$). $B_{d}$ is the concatenation of $T_{z}$ for $z\in[0\ldots r_{d}]$ in
decreasing order of $z$. See Figure 9 for a demonstration of $Ranks$, $Sizes$,
$Tails$, and the buckets.

Figure 9: A demonstration of the arrays constructed from $POR_{I}$ and the
structure of the buckets. Every cluster is presented as a suffix starting in
the first occurrence represented by the cluster.

We make the following simple observation.

######  Observation 76.

The size of every $T_{z}$ in the bucket $B_{q}$ is $s_{q}$.

The following directly follows.

######  Observation 77.

The size of $B_{q}$ is $s_{q}\cdot(r_{q}-r_{q+1})$ (with $r_{d+1}=-1$)

Using the above, we calculate the sizes of the buckets, and use them to
evaluate the starting index $i_{q}$ of every bucket $B_{q}$ within $I$. We
insert the starting indexes to a data structure for predecessor queries
$Bstarts$. For every cluster $C$, we denote the rank of $Tail(C)$ in $Tails$
as $tr(C)$. We initialize a data structure $Tlex$ for 2-d range counting
queries. For every cluster in $POR_{I}$, we add the point $(tr(C),|C|)$ to
$Tlex$. This concludes the construction of our data structure.

Upon query input $i$, we query $Bstarts$ for the predecessor of $i$ and obtain
$i_{z}$. We deduce that $i$ is within the bucket $B_{z}$. Let
$\ell_{z}=r_{z}-r_{z+1}$ be the number of $T$ sub-arrays contained in $B_{z}$.
For clearer presentation, we rename the $T$ sub-arrays contained in $B_{z}$
and denote $B_{z}=T^{z}_{0}\cdot T^{z}_{1}\ldots T^{z}_{\ell_{z}-2}\cdot
T^{z}_{\ell_{z}-1}$. It can be easily verified that $T^{z}_{q}=T_{r_{z}-q}$
for every $q\in[0\ldots\ell_{z}-1]$. Let $T^{z}_{r^{\prime}}$ be the sub array
in the concatenation of $B_{z}$ containing $i$. Since every $T^{z}_{q}$ has
the same size $s_{z}$, we can find the index $r^{\prime}$ by evaluating
$r^{\prime}=\lfloor\frac{i-i_{z}}{s_{z}}\rfloor$. Via the aforementioned
relation, we use $r^{\prime}$ to obtain an index $r$ such that $T_{r}$
contains $i$. We also calculate the index $i^{\prime}=i-i_{z}-s_{z}\cdot
r^{\prime}$ that satisfies $T_{r}[i^{\prime}]=I[i]$.

Our next task is to find the $i^{\prime}$th lexicographic suffix in $T_{r}$.
Recall that $T_{r}$ consists of the suffixes with rank $r$ from the clusters
of size at least $r+1$ sorted by increasing lexicographic order of the tails
of their corresponding clusters.

In order to find $T_{r}[i^{\prime}]$, we perform a ’restricted’ binary search
on $Tails$ using $Tlex$ (See Figure 10 for a demonstration). We start by
querying $Tlex$ for
$L=Count([1\ldots\frac{|POR_{I}|}{2}]\times[r+1\ldots\rotatebox{90.0}{8}{}])$.
The condition on the second coordinate ensures that only clusters with size at
least $r+1$ are counted. These are the clusters that have an implied
occurrence in $T_{r}$. The second coordinate condition is fixes for all the
queries of the binary search. If $L\geq i^{\prime}$ we deduce that
$T_{t}[i^{\prime}]$ is in the left half of $Tails$ and otherwise we deduce
that it is in the right half. We shrink the searched interval accordingly and
proceed recursively to finally obtain a tail $Tail(C)$ that is the
$i^{\prime}$th lexicographic tail among the tails of clusters participating in
$T_{r}$. We deduce that $T_{r}[i^{\prime}]$ is from the cluster of $t_{c}$,
denoted as $C=(a,b,p)$. Now we know the rank and the source cluster of $A[i]$,
so we can finally report $I[i]=a+(|C|-r-1)\cdot p$

Figure 10: A demonstration of the binary search executed using $Tlex$. The
clusters corresponding to circles above the $r+1$ horizontal line have a
represented occurrence that participates in $T_{r}$. Since the occurrences
appear in $T_{r}$ in lexicographic order of their clusters, we are interested
in finding the $i^{\prime}$ point from the left above this line.

Preprocess complexity: $Ranks$, $Sizes$ and the sizes and starting indexes of
the buckets can be evaluated in $\tilde{\mathcal{O}}(|POR_{I}|)$ time by
sorting the sizes of the clusters. Inserting the $O(|POR_{I}|)$ starting
indexes of buckets to $BStarts$ takes $\tilde{\mathcal{O}}(|POR_{I}|)$ using,
for example, a balanced search tree. $Tails$ can be obtained in
$\tilde{\mathcal{O}}(|POR_{I}|)$ time by sorting the tails of the clusters
with a standard $O(n\log n)$-comparisons sorting algorithm using $LCP$ queries
to compare between tails. Insertions to $Tlex$ are also polylogarithmic. The
space complexity is dominated by the space dedicated to the $2$ dimensional
data structure $Tlex$. It is bounded by
$O(|POR_{I}|\log(|POR_{I}|)=\tilde{\mathcal{O}}(|POR_{I}|)$. Recall that for
queries on $A_{w}$, we need to do a symmetric preprocessing for the set of
decreasing clusters too. The overall time and space complexity are both
$\tilde{\mathcal{O}}(|POR_{w}|)$.

Query time: In the process of finding $r$ and $i^{\prime}$, we use a
predecessor query and constant number of array lookups and basic arithmetic
operations to find $i_{z}$, $r^{\prime}$ and $|B_{z}|$. The complexity for
this part of the query is dominated by $(O(\log(|POR_{w}|))\subseteq
O(\log(n))$.

To find $T_{r}[i^{\prime}]$, we execute a restricted binary search on $Tails$.
We use a range query on $Tlex$ in every iteration of the binary search. A
2-dimensional counting query is executed in $O(\log^{2}(|POR_{w}|))$, so the
overall time complexity of this step is $O(\log^{3}(|POR_{w}|))\subseteq
O(\log^{3}(n))$.

We conclude this subsection with the following:

######  Theorem 78.

We can process a periodic clusters of occurrences $POR_{w}$ of a word $w$ in
$\tilde{\mathcal{O}}(|POR_{w}|)$ to support look-up queries for $A_{w}[i]$, in
$O(\log^{3}(n))$ time. As a side effect, our query can also output the indexes
$i^{\prime}$ and $r$ such that $A_{w}[i]=T_{r}[i^{\prime}]$ as well as the
cluster $C$ implying the occurrence starting in $A_{w}[i]$.

###  7.2 Extensions Restricting Range Counting

Let $POR_{w}$ be the periodic occurrences representation of a word
$w=S[s\ldots e]$. In this subsection we introduce the final ingredient for
Extensions Restricting Selection data structure:

Extension Restricting Range Counting
Input: $POR_{w}$ Query: for input integers $l,r,i,j$, return the amount of
$(l,r)$-extendable occurrences in $A_{w}[i\ldots j]$

Eventually, we will show that Extension Restricting Selection query can be
reduced to $\log(n)$ Extension Restricting Range Counting queries via a binary
search.

First, we recall that $A_{w}=D[1\ldots|D|]I[1\ldots|I|]$ with $D$ and $I$
being the sets of occurrences of $w$ represented by $POR_{w}$ implied by a
decreasing and by an increasing cluster, respectively. $A_{w}[i\ldots j]$ is
either a sub array of $I$, a sub array of $D$, or a concatenation of a suffix
of $D$ and a prefix of $I$. Therefore, it is sufficient to count
$(l,r)$-extendable occurrences in an interval within $D$ and an interval
within $I$.

We provide a data structure for counting $(l,r)$-extendable occurrences in an
interval within $I$. A similar algorithm can be constructed to count the
$(l,r)$-extendable occurrences within an interval in $D$.

####  7.2.1 Case 1: Periodic Extended Word

Let $p$ be the period of $w=S[s\ldots e]$. In this subsection, we deal with
the case in which $w^{\prime}=S[s-l\ldots e+r]$ also has a period $p$. In
these settings, we can use the following rule to decide if an occurrence of
$w$ is $(l,r)$-extendable:

######  Fact 79.

Let $C\in POR_{w}$ be a periodic cluster of occurrences of $w$. Let
$R_{C}=S[s_{C}\ldots e_{C}]$ and let $w_{t}=S[s_{t}\ldots e_{t}]$ be an
occurrence represented by $C$. Let $Ex^{t}_{l}=s_{1}-s_{r}$ be the length of
the part of $R_{C}$ to the left of $w_{t}$ and $Ex^{t}_{r}=e_{r}-e_{1}$ be
length of the part of $R_{C}$ to the right of $w_{t}$. $w_{t}$ is
$(l,r)$-extendable iff $Ex^{t}_{l}\geq l$ and $Ex^{t}_{r}\geq r$.

In words - $w_{t}$ is $(l,r)$-extendable iff $S[s_{t}-l\ldots e_{t}+r]$ is
contained within $R_{C}$. See Figure 11 for an illustration.

$\displaystyle w$$\displaystyle l$$\displaystyle r$$\displaystyle
w_{t}$$\displaystyle s_{C}$$\displaystyle e_{C}$$\displaystyle
l$$\displaystyle r$Run with period $\displaystyle p$$\displaystyle
R_{C}$$\displaystyle Ex^{t}_{l}$$\displaystyle Ex^{t}_{r}$

Figure 11: An illustration of Fact 79. $w$ has $l$ symbols to its left and $r$
symbols to its right contained within a run with period $p$. An occurrence
$w_{t}$ must have this property as well in order to be $(l,r)$-extendable.

Let $q_{R}$, $q_{L}$, $r_{R}<p$ and $r_{L}<p$ be the unique non negative
integers such that $r=q_{R}\cdot p+r_{R}$ and $l=q_{L}\cdot p+r_{L}$. Consider
a cluster $C=(a,b,p)\in POR_{I}$ with implied occurrences $w_{t}=S[s_{t}\ldots
e_{t}]$ starting in indexes $s_{t}=a+t\cdot p$ for $t\in[0\cdot|C|-1]$. We aim
to provide a characterization of the $(r,l)$-extendable occurrences within
$C$. For this purpose, we consider 3 types of occurrences represented by $C$:

  1. 1.

An occurrence $w_{t}$ is central if
$r_{p}(w_{t})\in[q_{R}+1\ldots|C|-q_{L}-2]$

  2. 2.

An occurrence $w_{t}$ is borderline if $|C|\geq q_{R}+q_{L}+1$ and
$r_{p}(w_{t})\in\\{q_{R},|C|-q_{L}-1\\}$

  3. 3.

An occurrence $w_{t}$ is marginal if it is neither central nor borderline.

Let $R_{C}=S[s_{C}\ldots e_{C}]$. We present the notation
$r_{L}(C)=s_{0}-s_{C}$ and $r_{R}(C)=e_{C}-e_{|C|-1}$. $r_{L}(C)$ (resp.
$r_{R}(C)$) is the remainder from the left (resp. right) of the run $R_{C}$
that is not contained within any of the occurrences in $C$.

######  Example 80.

In the text $S=bbbababbababbababbababbababaaa$, there is a cluster $C$ of
occurrences of $w=ababbababba$ with $R_{C}=S[2\ldots
27]=bbababbababbababbababbabab$. The prefix $bb$ of length $2$ of $R_{c}$
precedes the leftmost occurrence represented by $C$, therefore
$r_{L}(C)=2$.The suffix $bab$ with length $3$ of $R_{c}$ follows the rightmost
occurrence represented by $C$, therefore we have $r_{R}(C)=3$

We make the following simple Claim.

######  Claim 81.

An occurrence $w_{t}$ represented by a cluster $C$ has a part with length
exactly $(|C|-1-r_{p}(w_{t}))\cdot p+r_{L}(C)$ of $R_{C}$ to its left and a
part with length $r_{p}(w_{t})\cdot p+r_{R}(C)$ of $R_{C}$ to its right.

Proof: By definition, $w_{0}$ has a part of length exactly $r_{L}(C)$ of
$R_{C}$ to its left, which is consistent with our claim as
$r_{p}(w_{0})=|C|-1$. Every consecutive occurrence to the right has a period
rank lower by $1$, and a part with length longer by $p$ of $R_{C}$ to its left
(as it starts $p$ indexes to the right of the previous occurrence). This
inductively proves the correctness of our claim for all the occurrences
represented by $|C|$. The length of the extension to the right can be proven
in a symmetric manner. ∎

The following holds due to Fact 79

######  Lemma 82.

  1. 1.

Every central occurrence is an $(l,r)$-extendable occurrence.

  2. 2.

Every marginal occurrence is not an $(l,r)$-extendable occurrence.

  3. 3.

A borderline occurrence with $r_{p}(w_{t})=q_{R}<|C|-q_{L}-1$ is an
$(l,r)$-extendable occurrence iff $r_{R}(C)\geq r_{R}$

  4. 4.

A borderline occurrence with $r_{p}(w_{t})=|C|-q_{L}-1>q_{r}$ is an
$(l,r)$-extendable occurrence iff $r_{L}(C)\geq r_{L}$

  5. 5.

A borderline occurrence with $r_{p}(s_{t})=|C|-q_{L}-1=q_{r}$ is an
$(l,r)$-extendable occurrence iff $r_{L}(C)\geq r_{L}$ and $r_{R}(C)\geq
r_{R}$.

Proof: Applying Claim 81 and Fact 79 on every case yields the corresponding
result. ∎

Note that if $|C|<q_{L}+q_{R}+1$, all the occurrences are marginal
occurrences. So $C$ does not contain any $(l,r)$-extendable occurrences.

We recall the partition $I=T_{m},T_{m-1}\ldots T_{1},T_{0}$ as in the previous
section. Let $T_{r_{i}}$ be the sub array containing $i$ and $T_{r_{j}}$ be
the sub array containing $j$. And let $i_{r_{i}}$ and $j_{r_{j}}$ be two
indexes such that $T_{r_{i}}[i_{r_{i}}]=I[i]$ and $T_{r_{j}}[j_{r_{j}}]=I[j]$.
Every sub array $T_{r}$ with $r\in[r_{j}+1\ldots r_{i}-1]$ is fully contained
within $I[i\ldots j]$. Therefore, every occurrence with rank
$r\in[r_{j}+1\ldots r_{i}-1]$ is in $I[i\ldots j]$.

We define $5$ subsets of the $(l,r)$-extendable occurrences that a cluster $C$
may contribute to $I[i\ldots j]$:

  1. 1.

$Cent(C)$ \- Central occurrences $w_{t}$ with period rank
$r_{p}(w_{t})\in[r_{j}+1\ldots r_{i}-1]$.

  2. 2.

$Bor_{R}(C)$ \- an $(l,r)$-extendable borderline occurrence $w_{t}$ with
$r_{p}(w_{t})=q_{R}\in[r_{j}+1\ldots r_{i}-1]$

  3. 3.

$Bor_{L}(C)$ \- an $(l,r)$-extendable borderline occurrence $w_{t}$ with
$r_{p}(w_{t})=|C|-q_{L}-1\in[r_{j}+1\ldots r_{i}-1]$.

  4. 4.

$T_{r_{i}}(C)$ \- an $(l,r)$-extendable occurrence $w_{t}$ with
$r_{p}(w_{t})=r_{i}$

  5. 5.

$T_{r_{j}}(C)$ \- an $(l,r)$-extendable occurrence $w_{t}$ with
$r_{p}(w_{t})=r_{j}$

Note that apart from $Cent(C)$, all the listed sets are either of size $0$ or
of size $1$. Also note that the the union of these sets form the set of
$(l,r)$-extendable occurrences implied by $C$ in $I[i\ldots j]$, so our
problem is reduced to accumulating the sizes of these unions over all the
clusters in $POR_{I}$.

We start by considering the size of $Cent(C)$. Notice that only clusters with
$|C|\geq q_{R}+q_{L}+3$ have central occurrences.

######  Fact 83.

  1. 1.

If $|C|-q_{L}-2\geq r_{i}-1$, then $|Cent(C)|=r_{i}-1-max(r_{j},q_{R})$.

  2. 2.

If $q_{R}+q_{L}+3\leq|C|$ and $|C|-q_{L}-1<r_{i}-1$, then
$|Cent(C)|=|C|-q_{L}-2-max(r_{j},q_{R})$

Proof: The Central occurrences of $C$ are those with ranks in
$I_{cen}=[q_{R}+1\ldots|C|-q_{L}-2]$. $Cents(C)$ is the intersections of the
Central occurrences with the occurrences with rank in $I_{c}=[r_{j}+1\ldots
r_{i}-1]$ . This intersection is
$[max(r_{j}+1,q_{R}+1)\ldots\min(r_{i}-1,|C|-q_{L}-2)]$. The size of the
interval yields the formula ∎.

Next, we consider the sizes of $Bor_{R}(C)$ and $Bor_{L}(C)$. Note that each
of these sets can contain at most $1$ occurrence. Also note that only clusters
with $|C|\geq q_{R}+q_{L}+1$ have borderline occurrences.

The following facts hold directly from Lemma 82 and the definitions of
$Bor_{R}(C)$ and $Bor_{L}(C)$.

######  Fact 84.

If $|C|\geq q_{R}+q_{L}+2$:

  1. 1.

$Bor_{R}(C)$ and $Bor_{L}(C)$ are disjoint.

  2. 2.

We have $|Bor_{R}(C)|=1$ iff $r_{R}(C)\geq r_{R}$ and $q_{R}\in[r_{j}+1\ldots
r_{i}-1]$.

  3. 3.

We have $|Bor_{L}(C)|=1$ iff $r_{L}(C)\geq r_{L}$ and
$|C|-q_{L}-2\in[r_{j}+1\ldots r_{i}-1]$.

######  Fact 85.

If $|C|=q_{R}+q_{L}+1$:

  1. 1.

$Bor_{R}(C)=Bor_{L}(C)$

  2. 2.

$|Bor_{R}(C)|=1$ iff $r_{R}(C)\geq r_{R}$, $r_{L}(C)\geq r_{L}$ and
$q_{R}\in[r_{j}+1\ldots r_{i}-1]$.

Finally, we present a useful fact for evaluating the sizes of $T_{r_{i}}(C)$
and $T_{r_{j}}(C)$. These are also of size at most $1$. Recall that the
occurrences in $T_{r_{i}}$ and $T_{r_{j}}$ are sorted by lexicographical order
of the tails of their clusters. We denote as $C_{i}$ and $C_{j}$ be the
clusters representing $I[i]$ and $I[j]$, respectively. The following Facts
directly follow:

######  Fact 86.

Let $T_{z}[i_{z}\ldots j_{z}]$ be a subarray of some $T_{z}$. Let $C_{i_{z}}$
and $C_{j_{z}}$ be the clusters representing $T_{z}[i_{z}]$ and
$T_{z}[j_{z}]$, respectively. The cluster $C$ has an $(l,r)$ extendable
occurrence in $T_{z}[i_{z}\ldots j_{z}]$ iff the occurrence $w_{t}$ implied by
$C$ with $r_{p}(w_{t})=z$ is $(l,r)$-extendable and
$Tail(C_{i_{z}})\leq_{L}Tail(C)\leq_{L}Tail(C_{j_{z}})$.

Equipped with facts 83 \- 86, we can express the sum of the contributions of
all the clusters to $I[i\ldots j]$ as a set of $O(1)$ range queries. We recall
the notations of $tr(C)$ \- the lexicographic rank of $Tail(C)$ among the
clusters in $POR_{I}$. We initialize a $4$-dimensional range queries data
structures $Tlex$. For every cluster $C$, we insert the point
$p_{C}=(|C|,r_{L}(C),r_{R}(C),tr(C))$ with $v(p_{C})=|C|$ to $Tlex$.

######  Lemma 87.

The sum $\Sigma_{Cent}=\Sigma_{C\in POR_{I}}|Cent(C)|$ can be evaluated in
$O(\log^{4}(n))$ time given $Tlex$.

Proof: We make the following range queries on $Tlex$:

  1. 1.

$sum_{mid}=SUM([q_{L}+q_{R}+3\ldots
r_{i}+q_{L}]\times\ast\times\ast\times\ast)$

  2. 2.

$count_{mid}=COUNT([q_{L}+q_{R}+3\ldots
r_{i}+q_{L}]\times\ast\times\ast\times\ast)$

  3. 3.

$count_{large}=COUNT([max(r_{i}+q_{L}+1,q_{R}+q_{L}+3)\ldots\rotatebox{90.0}{8}{}]\times\ast\times\ast\times\ast)$

The ”$\ast$” symbol denotes the complete range of the corresponding coordinate
and is equivalent to $[-\rotatebox{90.0}{8}\ldots\rotatebox{90.0}{8}]$.
According to Fact 83, Every cluster $C$ such that $p_{C}$ is in the interval
counted in $count_{large}$ has $|Cent(C)|=r_{i}-1-max(r_{j},q_{R})$. So the
overall contribution of these clusters to $\Sigma_{Cent}$ is
$cont_{large}=count_{large}\cdot(r_{i}-1-max(r_{j},q_{R}))$

Every cluster $C$ such that the value of $p_{C}$ is accumulated in $sum_{mid}$
has $|Cent(C)|=|C|-q_{L}-2-max(r_{j},q_{R})$. The overall contribution of
these clusters to $\Sigma_{Cent}$ is
$cont_{mid}=sum_{mid}-count_{mid}\cdot(q_{L}+2+max(r_{j},q_{R}))$. We have
$\Sigma_{Cent}=cont_{mid}+cont_{large}$ since the clusters whose contributions
are considered in $const_{mid}$ are disjoint from the clusters considered in
$const_{large}$, and every cluster that was not considered in either of the
two is too small to have central occurrences. We used a constant number of
$4$-dimensional range queries so the time complexity is $O(\log^{4}(n))$. ∎

######  Lemma 88.

$\Sigma_{Bord}=\Sigma_{C\in POR_{I}}|Bor_{L}(C)\cup Bor_{R}(C)|$ can be
evaluated in $O(\log^{4}(n))$ time given $Tlex$.

Proof: We make the following range queries on $Tlex$:

  1. 1.

$count_{L}=COUNT([max(q_{R}+q_{L}+2,r_{j}+q_{L}+2)\ldots
r_{i}+q_{L}]\times[r_{L}\ldots\rotatebox{90.0}{8}{}]\times\ast\times\ast])$

  2. 2.

$count_{R}=COUNT([q_{R}+q_{L}+2\ldots\rotatebox{90.0}{8}{}]\times\ast\times[r_{R}\ldots\rotatebox{90.0}{8}{}]\times\ast])$.
If $q_{R}\notin[r_{j}+1\ldots r_{i}-1]$, we set $count_{R}=0$

  3. 3.

$count_{M}=COUNT([q_{R}+q_{L}+1\ldots
q_{R}+q_{L}+1]\times[r_{L}\ldots\rotatebox{90.0}{8}{}]\times[r_{R}\ldots\rotatebox{90.0}{8}{}]\times\ast])$.
If $q_{R}\notin[r_{j}+1\ldots r_{i}-1]$, we set $count_{M}=0$

Note that according to Fact 84, the point $p_{C}$ is counted in $count_{L}$
iff $|C|>q_{R}+q_{L}+2$ and $|Bor_{L}(C)|=1$, and the point $p_{C}$ is counted
in $count_{R}$ iff $|C|>q_{R}+q_{L}+2$ and $|Bor_{R}(C)|=1$. Fact 84 suggests
that $Bor_{L}(C)$ and $Bor_{L}(C)$ are distinct when $|C|\geq q_{L}+q_{R}+2$.
So the overall contribution of clusters with size at least $q_{R}+q_{L}+2$ to
$\Sigma_{Bord}$ is exactly $count_{L}+count_{R}$.

According to Fact 85, a point $p_{C}$ is counted in $count_{M}$ iff $C$ has a
single Borderline $(r,l)$-extendable occurrence $w_{t}$ with
$r_{p}(w_{t})=q_{r}$. It follows that the contribution of clusters with size
$q_{L}+q_{R}+1$ to $\Sigma_{Bord}$ is $count_{M}$. To summarize,
$\Sigma_{Bord}=count_{L}+count_{R}+count_{M}$. We use a constant number of
$4$-dimensional range queries to evaluate $\Sigma_{Bord}$, so the time
complexity is $O(\log^{4}(n))$. ∎

######  Lemma 89.

$\Sigma_{T}=\Sigma_{C\in POR_{I}}|T_{r_{i}}(C)\cup T_{r_{j}}(C)|$ can be
evaluated in $O(\log^{4}(n))$ time given $Tlex$.

Specifically, we prove the following:

######  Lemma 90.

Given an interval $[i_{z}\ldots j_{z}]$ and a period rank $z$, the amount of
$(l,r)$-extendable occurrences in $T_{z}[i_{z}\ldots j_{z}]$ can be evaluated
in $O(\log^{4}(n))$ time given $Tlex$.

Lemma 90 can be applied to either find $\Sigma_{C\in POR_{I}}|T_{r_{i}}(C)|$
and $\Sigma_{C\in POR_{I}}|T_{r_{j}}(C)|$ independently if $r_{i}\neq r_{j}$
or $\Sigma_{C\in POR_{I}}|T_{r_{i}}(C)|$ ($=\Sigma_{C\in
POR_{I}}|T_{r_{j}}(C)|$) if $r_{i}=r_{j}$.

Proof: Let $C_{i_{z}}$ and $C_{j_{z}}$ be the clusters containing
$T_{z}[i_{z}]$ and $T_{z}[j_{z}]$ respectively. If $z<q_{R}$, all the
occurrences with rank $z$ are Marginal, and therefore there are 0
$(l,r)$-extendable occurrences in $T_{z}$. Otherwise, we execute the following
range queries on $Tlex$:

  1. 1.

$count_{cent}=COUNT([z+q_{L}+2\ldots\rotatebox{90.0}{8}{}]\times\ast\times\ast\times[tr(C_{i_{z}})\ldots
tr(C_{j_{z}})])$

  2. 2.

$count_{bordL}=COUNT([z+q_{L}+1\ldots
z+q_{L}+1]\times[r_{L}\ldots\rotatebox{90.0}{8}{}]\times\ast\times[tr(C_{i_{z}})\ldots
tr(C_{j_{z}})])$

  3. 3.

$count_{bordR}=COUNT([q_{R}+q_{L}+2\ldots\rotatebox{90.0}{8}{}]\times\ast\times[r_{R}\ldots\rotatebox{90.0}{8}{}]\times[tr(C_{i_{z}})\ldots
tr(C_{j_{z}})])$

  4. 4.

$count_{bordM}=COUNT([q_{R}+q_{L}+1\ldots
q_{R}+q_{L}+1]\times[r_{L}\ldots\rotatebox{90.0}{8}{}]\times[r_{R}\ldots\rotatebox{90.0}{8}{}]\times[tr(C_{i_{z}})\ldots
tr(C_{j_{z}})])$

In all the above queries, the constraint on the last coordinate ensures that
we are only counting points that correspond to clusters $C$ with
$Tail(C_{i_{z}})<_{L}Tail(C)<_{L}Tail(C_{j_{z}})$. According to Fact 86, we
are interested in counting the clusters with this property, that also has an
$(l,r)$-extendable occurrence with degree $z$.

If $z=q_{R}$, every occurrence in $T_{z}$ is a borderline occurrence. For
arguments similar to the ones used in the evaluation of $\Sigma_{Bord}$, a
point $p_{C}$ is counted in $count_{bordR}$ iff $C$ has an $(l,r)$-extendable
occurrences with rank $q_{R}$ and $|C|\geq q_{R}+q_{L}+2$. Similarly, $p_{C}$
is counted in $count_{bordM}$ iff $C$ has an $(l,r)$-extendable occurrence
with rank $q_{R}$ and $|C|=q_{R}+q_{L}+1$. Overall, there are
$count_{bordR}+count_{bordM}$ $(l,r)$-extendable occurrences in
$T_{z}[i_{z}\ldots j_{z}]$ .

If $z\geq q_{R}+1$, an occurrence in $T_{z}[i_{z}\ldots j_{z}]$ can be a
borderline occurrence $w_{t}$ in a cluster $C$ with
$r_{p}(w_{t})=z=|C|-q_{L}-1$ in this case, $|C|=z+q_{L}+1\geq q_{R}+q_{L}+2$,
this occurrence is $(l,r)$-extendable iff $r_{L}(C)\geq r_{L}$. These
conditions are precisely described by the range counting query that was used
to yield $count_{bordL}$. Additionally, we need to count the clusters that
have a central occurrence in $T_{z}[i_{z}\ldots j_{z}]$. A cluster $C$ has a
central occurrence with degree $z$ iff $z\in[q_{R}+1\ldots|C|-q_{L}-2]$. In
this case, it is given that $z>q_{R}+1$, so our problem is reduced to counting
the clusters with $|C|>q_{L}+z+2$. This constrain is precisely described by
the range query used to evaluate $count_{cent}$. It is clear that the clusters
counted in $count_{bordL}$ and in $count_{cent}$ are disjoint, so
$count_{bordL}+count_{cent}$ is the number of $(l,r)$-extendable occurrences
in $T_{z}[i_{z}\ldots j_{z}]$.

We check if $z=q_{R}$ and return $count_{bordR}+count_{bordM}$ or
$count_{bordL}+count_{cent}$ accordingly. We used a constant number of
$4$-dimensional range queries, so the time complexity is $O(\log^{4}(n))$. We
also need to obtain $tr(C_{i_{z}})$ and $tr(C_{j_{z}})$. We can use Theorem 78
to obtain $C_{i_{z}}$ and $C_{j_{z}}$ in $O(\log^{3}(n))$ time. We store the
clusters such that every cluster is associated with the auxiliary information
$tr(C)$. ∎

We conclude this subsection with the following:

######  Theorem 91.

The periodic occurrences representation $POR_{w}$ of a word $w=S[s\ldots e]$
with $per(w)=p$ can be preprocessed in time $\tilde{\mathcal{O}}(|POR_{w}|)$
to answer Expression Restricting Range Counting queries of the form
$(l,r,i,j)$ in $O(\log^{4}(n))$ time, provided that $per(S[s-l\ldots e+r])=p$.
The generated data structure uses $\tilde{\mathcal{O}}(|POR_{w}|)$ space.

Proof: We preprocess $POR_{w}$ for $A_{w}$ lookup queries by employing Theorem
78. We also construct $Tlex$.

To process a query $(l,r,i,j)$ with $per(S[s-l\ldots e+r])=p$, we use the data
structure of Theorem 78 to obtain $T_{r_{i}}$, $T_{r_{j}}$, $i_{r_{i}}$,
$j_{r_{j}}$ and the clusters $C_{i}$ and $C_{j}$ containing $i$ and $j$
respectively. We also evaluate $q_{L}$, $q_{R}$, $r_{L}$ and $r_{R}$. We now
have all the data required to execute the range queries on $Tlex$ to evaluate
$\Sigma_{Bord}$, $\Sigma_{T}$ and $\Sigma_{Cent}$ by employing lemmas 87-89.
It can be easily verified that the sets of $(l,r)$-extendable occurrences
counted in $\Sigma_{Bord}$, in $\Sigma_{T}$ and in $\Sigma_{Cent}$ are
disjoint. We output thee sum $\Sigma_{Bord}+\Sigma_{T}+\Sigma_{Cent}$.

Preprocessing time and space: The construction of the data structure for
$A_{w}$ look-ups takes $\tilde{\mathcal{O}}(POR_{w})$ time and space by
Theorem 78. The arguments required to construct the points of $Tlex$ can be
evaluated by calculating $|C|$, $r_{L}(C)$ and $r_{R}(C)$ in $O(1)$ for every
cluster $|C|$, and sorting the tails to get $tr(C)$ for every cluster $C$. We
then insert every one of the $|POR_{w}|$ points to $Tlex$ in $O(\log^{4}(n))$.
The overall time is $\tilde{\mathcal{O}}(|POR_{w}|)$, and so is the space of
the generated data structure.

Query time: The query consists of two lookup queries in $A_{w}$, a constant
number of arithmetic operations to evaluate $q_{R}$, $q_{L}$, $r_{R}$ and
$r_{L}$, and a single applications of each of lemmas 87-89. The time is
bounded by $O(\log^{4}(n))$. ∎

####  7.2.2 Case 2: An A-periodic Extended Word

In this subsection, we examine the case in which $w^{\prime}=S[s-l\ldots e+r]$
does not have a period $per(w)=p$. We show that in this case, every cluster
contributes at most a single $(l,r)$-extendable occurrence to $A_{w}[i\ldots
j]$. Let $R=S[s-E_{l}\ldots e+E_{r}]$ be the run with period $p$ containing
$w$. Let $q_{L},q_{R},r_{R},r_{L}$ defined as in the previous section, and
similarly let $q_{E_{L}}$, $q_{E_{r}}$, $r_{E_{l}}<p$ and $r_{E_{r}}<p$ be non
negative integers such that $E_{l}=q_{E_{l}}\cdot p+r_{E_{l}}$ and
$E_{r}=q_{E_{r}}\cdot p+r_{E_{r}}$.

Note that if $w^{\prime}$ does not have a period $p$, it must be the case that
either $r>E_{r}$ or $l>E_{l}$. Let $C_{w}$ be the periodic cluster containing
$w$. The following facts are the key for efficiently executing Restricted
Range Counting Queries:

######  Fact 92.

If $l>E_{l}$ and $r\leq E_{r}$, only an occurrence $w_{t}$ implied by cluster
$C$ with period rank $r_{p}(w_{t})=|C|-q_{E_{l}}-1$ can be $(l,r)$-extendable.
This $w_{t}$ is $(l,r)$-extendable iff one of these conditions hold:

  1. 1.

$LCS(Head(C),Head(C_{w}))\geq l-p\cdot q_{E_{l}}$ and $|C|\geq
q_{E_{l}}+q_{R}+2$

  2. 2.

$LCS(Head(C),Head(C_{w}))\geq l-p\cdot q_{E_{l}}$ , $|C|=q_{E_{l}}+q_{R}+1$
and $r_{R}(C)\geq r_{R}$

######  Fact 93.

If $l\leq E_{l}$ and $r>E_{r}$, only an occurrence $w_{t}$ implied by cluster
$C$ with period rank $r_{p}(w_{t})=q_{E_{r}}$ can be $(l,r)$-extendable. This
$w_{t}$ is $(l,r)$-extendable iff one of these conditions hold:

  1. 1.

$LCP(Tail(C),Tail(C_{w}))\geq r-p\cdot q_{E_{r}}$ and $|C|\geq
q_{L}+q_{E_{r}}+2$

  2. 2.

$LCP(Tail(C),Tail(C_{w}))\geq r-p\cdot q_{E_{r}}$ , $|C|=q_{L}+q_{E_{r}}+1$
and $r_{L}(C)\geq r_{L}$

######  Fact 94.

If $l>E_{l}$ and $r>E_{r}$, only an occurrence $w_{t}$ implied by cluster $C$
with period rank $r_{p}(w_{t})=q_{E_{r}}$ can be $(l,r)$-extendable. This
$w_{t}$ is $(l,r)$-extendable iff $|C|=q_{E_{l}}+q_{E_{r}}+1$,
$LCP(Tail(C),Tail(C_{w}))\geq r-p\cdot q_{E_{r}}$ and
$LCS(Head(C),Head(C_{w}))\geq l-p\cdot q_{E_{l}}$

$\displaystyle w$$\displaystyle l$$\displaystyle r$$\displaystyle
w_{t}$$\displaystyle s_{C}$$\displaystyle e_{C}$$\displaystyle
l$$\displaystyle r$$\displaystyle Run_{C_{w}}$$\displaystyle
Run_{C}$$\displaystyle Ex^{t}_{l}$$\displaystyle Ex^{t}_{r}$$\displaystyle
Head(C_{w})$$\displaystyle E_{l}$$\displaystyle Head(C)$

Figure 12: An illustration of Fact 92. $w$ has $r$ symbols to its right
contained within $Run_{C_{w}}$. To its left, the first $Ex_{l}$ symbols are
within $Run_{C_{w}}$ and the following $l-Ex_{l}$ symbols are a suffix of
$Head(C_{w})$. An occurrence $w_{t}$ implied by cluster $C$ must have a
similar relation to $Run_{C}$ in order to be $(l,r)$-extendable. Additionally,
$Head(C)$ must have a sufficiently long agreement with $Head(C_{w})$. In this
demonstration, $Head(C)$ starts to the left of $Run(C)$. Note that it does not
have to be the case, and a portion of $Head(C)$ may be contained within
$Run(C)$.

The intuition behind facts 92 \- 94 is the following. An occurrence
$w_{0}=S[i_{0}\ldots j_{0}]$ of $w$ has period $p$. For $w_{0}$ to be
$(l,r)$-extendable, it must agree with $w^{\prime}$ on the extension of the
period $p$ around $w_{0}$ (at least within $w_{0}=S[i_{0}-l\ldots j_{0}+r]$).
Furthermore, there must be a sufficiently long agreement between the non
periodic ’left overs’. For an illustration, see Figure 12. We provide a proof
for Fact 92, facts 93 and 94 can be proven by using similar arguments.

Proof: Let $w_{t}=S[s_{t}\ldots e_{t}]$ be an occurrence implied by $C$, and
let the run with period $p$ containing $C$ be $R=S[s_{C}\ldots e_{C}]$. Recall
that the size of the extension of $R$ to the left of $w_{t}$ is
$(|C|-1-r_{p}(w_{t}))\cdot p+r_{L}(C)$ (Claim 81).

We start by proving the following claim.

######  Claim 95.

An $(l,r)$-extendable occurrence $w_{t}$ implied by $C$ must have
$r_{p}(w_{t})=|C|-q_{E_{l}}-1$ .

Proof: If $r_{p}(w_{t})<|C|-q_{E_{l}}-1$, the extension of $R$ to the left
from $w_{t}$ is at least $(q_{E_{l}}+1)\cdot p>q_{E_{l}}\cdot
p+r_{E_{l}}=E_{l}$ and therefore, (according to Lemma 36)
$lcs(s_{t}-1,s-1)=E_{l}<l$ so $w_{t}$ is not $(l,r)$-extendable.

If $r_{p}(w_{t})>|C|-q_{E_{l}}-1$, the extension of $R$ to the left from
$w_{t}$ is at most $(q_{E_{l}}-1)\cdot p<q_{E_{l}}\cdot p+r_{E_{l}}=E_{l}$.
Therefore, $lcs(s-1,s_{t}-1)<E_{l}<l$ and $w_{t}$ is not $(l,r)$-extendable.
We get that for $w_{t}$ to be $(l,r)$ extendable, it must have
$r_{p}(w_{t})=|C|-q_{E_{l}}-1$. ∎

We proceed with the following claim:

######  Claim 96.

An occurrence $w_{t}$ with $r_{p}(w_{t})=|C|-q_{E_{l}}-1$ has
$lcs(s-1,s_{t}-1)\geq l$ iff $lcs(Head(C_{w}),Head(C))\geq l-p\cdot q_{E_{l}}$

Proof: If $r_{p}(w_{t})=|C|-q_{E_{l}}-1$, $w_{t}$ has a (not necessarily
maximal) interval with period $p$ of size $q_{E_{l}}\cdot p$ to its left,
proceeded by $Head(C)$. $w$ has the same structure - it has a periodic
interval of size at least $q_{E_{l}}\cdot p$ to its left proceeded by
$Head(C_{w})$. Comparing from right to left, the suffixes $S^{s_{t}-1}$ and
$S^{s-1}$ match within the periodic interval. Therefore we have
$S[s_{t}-p\cdot q_{E_{l}}\ldots s_{t}-1]=S[s-p\cdot q_{E_{l}}\ldots s-1]$.
From this point, we are comparing between the heads of $C$ and $C_{w}$. So
$lcs(s_{t}-1,s-1)=lcs(Head(C_{w}),Head(C))+p\cdot q_{E_{l}}$ and we need
$lcs(Head(C_{w}),Head(C))\geq l-p\cdot q_{E_{l}}$ for $w_{t}$ to have a
sufficiently long agreement the left with $w$. ∎

Let $w_{t}$ be an occurrence represented by a cluster $C$ with
$lcs(Head(C_{w}),Head(C))\geq l-p\cdot q_{E_{l}}$. According to the above
claim, $w_{t}$ is sufficiently extendable to the left to be an $(l,r)$
extendable occurrence. We consider the following cases for the size of $C$.

If $|C|<q_{E_{l}}+q_{R}+1$, the extension of $w_{t}$ with
$r_{p}(w_{t})=|C|-q_{E_{l}}-1$ to the right is at most $(q_{R}-1)\cdot
p<q_{R}+r_{R}=r$. Since $E_{r}\geq r$, Lemma 36 yields $lcp(e+1,e_{t}+1)<r$
and $w_{t}$ is not $(l,r)$-extendable.

If $|C|\geq q_{E_{l}}+q_{R}+2$, the extension of $R$ to the right of $w_{t}$
with $r_{p}(w_{t})=|C|-q_{E_{l}}-1$ is at least $(q_{R}+1)\cdot
p>q_{R}+r_{R}=r$. Since $E_{r}\geq r$, the period $p$ extends at least $r$
indexes both to the right of $w_{t}$ and to the right of $w$. It follows that
$lcp(e+1,e_{t}+1)\geq r$ and $w_{t}$ is sufficiently extendable from the right
making it an $(l,r)$-extendable occurrence.

If $|C|=q_{E_{l}}+q_{R}+1$, $w_{t}$ has an extension of $Run_{C}$ of size
exactly $q_{R}\cdot p+r_{R}(C)$ to its right. Since $E_{r}\geq r$ We need the
period $p$ to extend at least $r=q_{R}\cdot p+r_{R}$ indexes to the right of
$w_{t}$ for it to be sufficiently extendable to the right. Therefore, in this
case $w_{t}$ is $(l,r)$-extendable iff $r_{R}(C)\geq r_{R}$. ∎

Equipped with facts 92 \- 94, we are ready to formulate the problem as a set
of range queries. We construct a data structure for $6$-dimensional range
queries $Tlex$. For every cluster $C$, we insert the point:

$p_{C}=(|C|,r_{L}(C),r_{R}(C),lcs(Head(C),Head(C_{w})),lcp(Tail(C),Tail(C_{w})),tr(C))$

More precisely, we will present our queries as if they are executed on the
aforementioned $6$-dimensional data structure. We will never use more than $4$
non-trivial ranges (”$\ast$”) in a single query, so it is sufficient to store
a set of $4$-dimensional data structures, each containing a different subsets
of the coordinates of the points $p_{C}$ that is required for a certain query.

Let our input Extension Restricting Range Query be $(l,r,i,j)$. We recall the
notations of $T_{r_{i}}$,$T_{r_{j}}$, $i_{r_{i}}$ and $j_{r_{j}}$ such that
$T_{r_{i}}[i_{r_{i}}]=I[i]$ and $T_{r_{j}}[j_{r_{j}}]=I[j]$, as well as
$C_{i}$ and $C_{j}$ the clusters respectively implying the occurrences
starting in $I[i]$ and in $I[j]$. We distinguish between three cases with each
case corresponding to one of the facts 92 \- 94.

Case 1: $l>E_{l}$ and $r\leq E_{r}$. We start by counting the
$(l,r)$-extendable occurrences in $T_{z}$ for $z\in[r_{j}+1\ldots r_{i}-1]$.
To do that, we execute the following range queries on $Tlex$-

  1. 1.

$count_{mid1}=COUNT([max(q_{E_{l}}+r_{j}+2,q_{E_{l}}+q_{R}+2)\ldots
q_{E_{L}}+r_{i}]\times\ast\times\ast\times[l-q_{E_{L}}\cdot
p)\ldots\rotatebox{90.0}{8}{}]\times\ast\times\ast)$

  2. 2.

$count_{mid2}=COUNT(q_{E_{l}}+q_{R}+1\ldots
q_{E_{l}}+q_{R}+1]\times\ast\times[r_{R}\ldots\rotatebox{90.0}{8}]\times[l-q_{E_{L}}\cdot
p)\ldots\rotatebox{90.0}{8}{}]\times\ast\times\ast)$. We set $count_{mid2}=0$
if $q_{R}\notin[r_{j}+1\ldots r_{i}-1]$.

$count_{mid1}$ counts occurrences from clusters $C$ with $|C|\geq
q_{E_{l}}+q_{R}+2$ and $LCS(Head(C_{w},C))\geq l-q_{E_{l}}\cdot p$ \- these
are $(l,r)$-extendable occurrences that correspond to the first condition in
Fact 92. The additional constraint on $|C|$ ensures that
$|C|-q_{E_{l}}-1\in[r_{j}+1\ldots r_{i}-1]$. Therefore, $count_{mid1}$ counts
the amount of $(l,r)$-extendable occurrences $w_{t}$ corresponding to the
first condition of Fact 92 with $r_{p}(w_{t})=|C|-q_{E_{l}}-1\in[r_{j}+1\ldots
r_{i}-1]$.

$count_{mid2}$ counts $(l,r)$-extendable occurrences that correspond to the
second condition. Every $(l,r)$-extendable occurrence $w_{t}$ in this case has
rank $r_{p}(w_{t})=|C|-q_{E_{l}}-1=q_{R}$. Since we nullify $count_{mid2}$ if
$q_{R}\notin[r_{j}+1\ldots r_{i}-1]$, we get that $count_{mid2}$ counts the
$(l,r)$-extendable occurrences that corresponds to the second condition and
are within the relevant interval of ranks.

Overall, $count_{mid1}+count_{mid2}$ is the number of $(l,r)$-extendable
occurrences in $T_{z}$ for $z\in[r_{j}+1\ldots r_{i}-1]$.

We are left with the tasks of counting the $(l,r)$-extendable occurrences in
the parts of $T_{r_{i}}$ and $T_{r_{j}}$ that are contained in $I[i\ldots j]$.
As in the periodic case, this is easily reducible to counting the
$(l,r)$-extendable occurrences within a given interval $T_{z}[i_{z}\ldots
j_{z}]$ of a sub-array $T_{z}$.

As in the periodic case, we construct a range query to count the
$(l,r)$-extendable occurrences within an interval $T_{z}[i_{z}\ldots j_{z}]$
in $T_{z}$. Let $C_{i}$ and $C_{j}$ be the clusters implying $T_{z}[i_{z}]$
and $T_{z}[j_{z}]$, respectively. We execute the following range query on
$Tlex$:

  1. 1.

$count_{1}=COUNT([z+q_{L}+1\ldots
z+q_{L}+1]\times\ast\times\ast\times[L-q_{E_{L}}\cdot
p\ldots\rotatebox{90.0}{8}]\times\ast\times[tr(C_{i})\ldots tr(C_{j})])$

  2. 2.

$count_{2}=COUNT([z+q_{L}+1\ldots
z+q_{L}+1]\times\ast\times[r_{R}\ldots\rotatebox{90.0}{8}]\times[L-q_{E_{L}}\cdot
p\ldots\rotatebox{90.0}{8}]\times\ast\times[tr(C_{i})\ldots tr(C_{j})])$

We proceed to make the following claims regarding $count_{1}$ and $count_{2}$.

######  Claim 97.

A cluster $C$ implies an $(l,r)$-extendable occurrence in $T_{z}$ iff
$|C|=q_{E_{l}}+z+1$ and it implies an $(l,r)$-extendable occurrence.

Proof: We start by proving $\xrightarrow[]{}$. Let $w_{t}$ be an
$(l,r)$-extendable occurrence in $T_{z}$ implied by cluster $C$. According to
Lemma 92, $w_{t}$ must have $r_{p}(w_{t})=|C|-q_{E_{l}}-1$. Since $w_{t}$ is
in $T_{z}$, it must have $r_{p}(w_{t})=z$. By transitivity, we get
$|C|-q_{E_{l}}-1=z$ which implies $|C|=q_{E_{l}}+z+1$.

We proceed to prove $\xleftarrow[]{}$. Let $w_{t}$ be an $(l,r)$-extendable
occurrence implied by $C$, with $|C|=q_{E_{l}}+z+1$. Lemma 92 suggests that
$r_{p}(w_{t})=z$ ∎

######  Claim 98.

If $z\geq q_{R}+1$, The number of $(l,r)$-extendable occurrences in
$T_{z}[i_{z}\ldots j_{z}]$ is $count_{1}$.

Proof: The constraint on the first coordinate ensures that the clusters
counted by $count_{1}$ are with size $q_{E_{l}}+z+1$.

If $q_{E_{l}}+z+1\geq q_{E_{l}}+q_{R}+2$, the first case of Lemma 92 applies
and every cluster $C$ with $|C|=q_{E_{l}}+z+1$ contains an $(l,r)$-extendable
occurrence iff $lcs(Head(C),Head(C_{w}))\geq L-q_{E_{L}}\cdot p$. the
constraint on the $4$th coordinate ensures that we are only counting clusters
that contain an $(l,r)$-extendable occurrence.

So far, we have shown that points satisfying the constraints on the first and
on the $4$th coordinates corresponds to the set of clusters with size
$q_{E_{l}}+z+1$ and containing an $(l,r)$-extendable occurrence. Claim 97
suggests that this is exactly the set of clusters that contains an
$(l,r)$-extendable occurrence in $T_{z}$.

Finally, the constraint on $tr(C)$ ensures that we only count clusters $C$
with $tr(C_{i})\leq tr(C)\leq tr(C_{j})$. Since the occurrences $T_{z}$ are
sorted by the lexicographic order of the tails of their clusters, that
constraint ensures that we only count clusters with an $(l,r)$-extendable
occurrence in $T_{z}[i_{z}\ldots j_{z}]$ ∎

######  Claim 99.

If $z=q_{R}$, the number of $(l,r)$-extendable occurrences in
$T_{z}[i_{z}\ldots j_{z}]$ is $count_{2}$.

Proof: The constraint on the first coordinate ensures that the clusters
counted by $count_{1}$ are with size $q_{E_{l}}+z+1$.

If $z=q_{R}$, the second case of Lemma 92 applies and every cluster $C$ with
$|C|=q_{E_{l}}+z+1$ contains an $(l,r)$-extendable occurrence with degree $z$
iff $lcs(Head(C),Head(C_{w}))\geq L-q_{E_{L}}\cdot p$ and $r_{R}(C)\geq
r_{R}(C_{w})$. The constraints on the third and on the forth coordinates
ensures that we only count clusters that imply an $(l,r)$-extendable
occurrence.

So far, we have shown that points satisfying the constraints on the first, the
third and the $4$th coordinates corresponds to the set of clusters with size
$q_{E_{l}}+z+1$ that contain an $(l,r)$-extendable occurrence. Claim 97
suggests that this is exactly the set of clusters that contains an
$(l,r)$-extendable occurrence in $T_{z}$.

As in the proof of Claim 98, the constraint on $tr(C)$ ensures that we only
count clusters with an $(l,r)$-occurrence within the interval
$T_{z}[i_{z}\ldots j_{z}]$ in $T_{z}$. ∎

######  Claim 100.

If $z<q_{R}$, there are no $(l,r)$-extendable occurrences in
$T_{z}[i_{z}\ldots j_{z}]$.

Proof: Assume to the contrary that $T_{z}$ contains an $(l,r)$-extendable
occurrence $w^{\prime}$ implied by a cluster $C^{\prime}$. Claim 97 suggests
that that $r_{p}(w_{t})=|C^{\prime}|-q_{E_{l}}-1$. Since $w_{t}$ is in
$T_{z}$, we get $z=|C^{\prime}|-q_{E_{l}}-1$. From our assumption that
$z<q_{R}$ we get $|C^{\prime}|<q_{E_{l}}+q_{R}+1$. This is a contradiction to
Lemma 92, in which both cases require $|C^{\prime}|\geq q_{E_{l}}+q_{R}+1$. ∎

With claims 98-100, it is straightforward to construct an algorithm for
counting $(l,r)$-extendable occurrence within $T_{z}[i_{Z}\ldots j_{z}]$. We
compare $z$ to $q_{R}$. If $z\geq q_{R}+1$\- we compute $count_{1}$ and return
it (Claim 98). If $z=q_{R}$ we compute $count_{2}$ and return it (Claim 99).
If $z<q_{R}$ we simply return $0$ (Claim 100). We execute at most a single
range query in the process of reporting the number of $(l,r)$-extendable
occurrences within $T_{z}[i_{z}\ldots j_{z}]$. The time complexity is
therefore $O(\log^{4}(n))$

Case 2: $l\leq E_{l}$ and $r>E_{r}$. This case is corresponding to Lemma 93
and is handled symmetrically to case 1.

Case 3: $l>E_{l}$ and $r>E_{r}$. Again, we start by counting the
$(l,r)$-extendable occurrences in $T_{z}$ for $z\in[r_{j}+1\ldots r_{i}-1]$.
Note that in this case, according to Fact 94, the only acceptable rank for an
$(l,r)$-extendable occurrence is $q_{E_{r}}$, and the only acceptable size for
a cluster containing an $(l,r)$ extendable occurrence is
$q_{E_{l}}+q_{E_{r}}+1$. if $q_{E_{r}}\in[r_{j}+1\ldots r_{i}-1]$, we query:

$count=COUNT(q_{E_{l}}+q_{E_{r}}+1\ldots
q_{E_{l}}+q_{E_{r}}+1]\times\ast\times\ast\times[l-q_{E_{l}}\cdot
p\ldots\rotatebox{90.0}{8}{}]\times[r-q_{E_{r}}\cdot
p\ldots\rotatebox{90.0}{8}{}]\times\ast)$.

According to Fact 94, these are all the $(l,r)$-extendable occurrences of $w$.
Since $T_{q_{E_{r}}}$ is completely contained within $I[i\ldots j]$, all of
these occurrences are in $I[i\ldots j]$ and we output $count$.

If $q_{E_{r}}\in\\{r_{i},r_{j}\\},$ we have $T_{q_{E_{r}}}$ only partially
contained in $I[i\ldots j]$. We need to count $(l,r)$-extendable occurrences
within a certain interval $T_{q_{E_{r}}}[i_{z}\ldots j_{z}]$ with $C_{i_{z}}$
and $C_{j_{z}}$ the clusters implying the occurrences starting in
$T_{q_{E_{r}}}[i_{z}]$ and in $T_{q_{E_{r}}}[j_{z}]$ respectively. We query:

$count=COUNT([q_{E_{l}}+q_{E_{r}}+1\ldots
q_{E_{l}}+q_{E_{r}}+1]\times\ast\times\ast\times[l-q_{E_{l}}\cdot
p\ldots\rotatebox{90.0}{8}{}]\times[r-q_{E_{r}}\cdot
p\ldots\rotatebox{90.0}{8}{}]\times[tr(C_{i_{z}})\ldots tr(C_{j_{z}}))$.

$count$ counts only the $(l,r)$-extendable occurrences within
$T_{q_{E_{r}}}[i_{z}\ldots j_{z}]$ since the occurrences in $T_{q_{E_{r}}}$
are sorted by the lexicographic order of their clusters’ tails.

The following theorem concludes the result of this subsection:

######  Theorem 101.

The periodic occurrences representation $POR_{w}$ of a word $w=S[s\ldots e]$
with $per(w)=p$ can be preprocessed in time $\tilde{\mathcal{O}}(|POR_{w}|)$
to answer Extension Restricting Range Counting queries of the form $(l,r,i,j)$
in $O(\log^{4}(n))$ time, provided that $per(S[s-l\ldots e+r])\neq p$.

Proof: We preprocess $POR_{w}$ for look-ups in $A_{w}[i]$ using Theorem 78. We
process every cluster $C$ to obtain $|C|$, $r_{L}(C)$, $r_{R}(C)$,
$lcs(Head(C),Head(C_{w}))$ and $lcp(Tail(C),Tail(C_{w}))$. We sort the tails
of the clusters to obtain $tr(C)$ for every cluster $C$. Now we have the
required data to construct the point $p_{C}$ for every cluster. We insert
subsets of size at most $4$ of the coordinates of $p_{C}$ to several
$4$-dimensional range queries data structures corresponding to the coordinates
with non-trivial intervals in the queries described in this section. We also
evaluate $E_{r}$ and $E_{l}$ the extensions of the run with period $p$ to the
right and to the left of $w$, respectively.

Upon a query $(l,r,i,j)$, we classify the query into one of the 3 cases
described in this section. We execute a look-up query to $I[i]$ and $I[j]$ to
obtain $T_{r_{i}}$,$T_{r_{j}}$, $i_{r_{i}}$, $j_{r_{j}}$, $C_{i}$ and $C_{j}$.
We now have all the information required to execute the range queries.

Preprocessing time: The time for constructing a data structure for $I[i]$ look
ups is $\tilde{\mathcal{O}}(|POR_{w}|)$. Every cluster in $POR_{w}$ is
processed with a constant number of $LCE$ queries and basic arithmetic
operation, which are all polylogarithmic operations. Sorting the tails of the
clusters takes $\tilde{\mathcal{O}}(|POR_{w}|)$. Finally, inserting all the
(partial) points to $4$-dimensional range queries data structures takes
polylogarithmic time per point. The overall complexity is
$\tilde{\mathcal{O}}(|POR_{w}|)$.

Query time: The query time consists of a constant amount of comparison
operations to classify the query, two look-up queries for $I$ and a constant
amount of $4$-dimensional range queries. The complexity is dominated by
$O(\log^{4}(n))$.

Recall that a similar data structure needs to be constructed for the subarray
$D$ of $A_{w}$ containing occurrences from decreasing clusters. ∎

Putting it together with Theorem 91, we get the following:

######  Theorem 102.

The periodic occurrences representation $POR_{w}$ of a word $w=S[s\ldots e]$
can be preprocessed in time $\tilde{\mathcal{O}}(|POR_{w}|)$ to answer
Extension Restricting Range Counting queries in $O(\log^{4}(n))$ time.

Proof: given a query $(l,r,i,j)$, we can check if $l\leq E_{l}$ and $r\leq
E_{r}$. If both are true, we employ Theorem 91. Otherwise, we employ Theorem
101. The classification test takes additional constant time. ∎

We can use the above result to finally prove Theorem 28

Proof: We preprocess $POR_{w}$ for $A_{w}$ look-up queries and for Extension
Restricting Range Counting queries with theorems 78 and 102.

Upon a query for $A_{w}^{(l,r)}[i]$, we execute a binary search for the index
$i^{\prime}$ such that $A_{w}[i^{\prime}]=A_{w}^{(l,r)}[i]$ as follows: start
by executing the Extension Restricting Range Counting query
$(l,r,1,\frac{|A_{w}|}{2})$. Denote the output of the query as $L$. If $L\geq
i$ we deduce that $A_{w}^{(l,r)}[i]$ is in $A_{w}[1\ldots\frac{|A_{w}|}{2}]$.
Otherwise, we deduce that $A_{w}^{(l,r)}[i]$ is in
$A_{w}[\frac{|A_{w}|}{2}+1\ldots|A_{w}|]$. We shrink our search range and
proceed recursively until our search interval is of size $1$. The sole index
in the final interval is $i^{\prime}$. We conclude by returning
$A_{w}[i^{\prime}]$

The preprocessing time and the space consumed by the data structure are both
bounded by $\tilde{\mathcal{O}}(|POR_{w}|)$ directly from Theorem 78 and
Theorem 102. The query time consists of $\log(n)$ binary search iterations
($|A_{w}|\leq n$). In every iteration of the binary search we execute an
Extensions Restricting Range Counting query costing $O(\log^{4}(n))$ time
each. We conclude with a single look-up query in $A_{w}$. The time complexity
is dominated by $O(\log^{5}(n))$. ∎

##  8 Maintaining Indexed Integers Under Batched Updates

In this section, we provide proofs for Claim 33 and Theorem 2.

###  8.1 Proof of Claim 33

See 33

Claim 33 may be considered as folklore and can be solved via the following
well known, simple construction. $C$ can be represented as a full binary tree
with $n$ leaves and weighted edges. The $k$’th leaf from the right represents
$C[k]$ and the sum of the edges from the root to that leaf equals to $C[k]$.
Upon update $(i,j,x)$, a set of $O(\log(n))$ edges can be identified such that
every leaf $l$ in position $[i\ldots j]$ from the left has exactly one of
these edges in the route from $l$ to the root, and every other leaf does not
have any of these edges in its route to the root. Therefore, increasing the
weights of these edges by $x$ will have the desired effect.

This set of edges can be identified by constructing the paths from $i$ and
from $j$ to the root. The lowest common ancestor $lca(i,j)$ of the leaves $i$
and $j$ is the lowest node to appear in both paths. For every node $u$ in the
sub - path from $lca(i,j)$ to $i$ (not including $lca(i,j)$), if the right
edge emerging from $u$ is not a part of the path - add it to the set. For
every node $v$ in the path from $lca(i,j)$ to $j$ \- if the left node emerging
from $v$ is not in the path - add it to the set. In both cases- include the
edge entering the leaf in the set. It can be easily verified that this
construction yields a set with the required property and can be found in
$O(\log(n))$ time.

###  8.2 Proof of Theorem 2

See 2

We denote the set of maintained counters as $C[1\ldots n]$. We assume that all
the counters are initially set to $C[i]=0$. Any other initialization of $C$
can be easily supported by keeping the initial values in a static array $A$
and a stairs updates data structure $D$ with initialized values $D[i]=0$. Upon
a lookup query for $C[i]$, we report $C[i]=A[i]+D[i]$.

Our data structure for restricted decreasing stairs updates works as follows:
We maintain two range queries data structure. A 2-dimensional data structure
$O$ and a 3-dimensional data structure $R$. Note that $p$ is fixed among all
the updates, so it does not need to be specified in the query.

Upon a query for applying a decreasing stairs update $(i,j)$ we insert the
point $p_{O}=(i,j)$ with the value $v(p_{O})=\lceil\frac{j}{p}\rceil$ to $O$,
and the point $p_{R}=(i,j,(j\bmod p))$ (with an arbitrary value assigned to
$v(p_{R})$) to $R$. If $(j\bmod p)=0$ we set the third coordinate of $p_{R}$
to be $p$ instead.

Upon a query for reporting the value of $C[x]$, we evaluate the unique
positive integers $q_{x}$ and $r_{x}$ such that $x=q_{x}\cdot p+r_{x}$ with
$r_{x}<p$. We execute the following range queries:

  1. 1.

Query $O$ for $S=SUM([1\ldots x]\times[x\ldots n])$

  2. 2.

Query $O$ for $C=COUNT([1\ldots x]\times[x\ldots n])$

  3. 3.

Query $R$ for $D=COUNT([1\ldots x]\times[x\ldots n]\times[1\ldots r_{x}-1])$.
If $r_{x}=0$, we set $D=0$

We return $S-C\cdot q_{x}-D$.

######  Lemma 103.

$C[x]=S-C\cdot q_{x}-D$

Proof: We denote $con_{j}(k)$ to be the value that a decreasing stairs update
$(i,j,p)$ adds to index $k$, assuming that $k\in[i\ldots j]$. If $k>j$, the
value of $con_{j}(k)$ is undefined and allowed to be an arbitrary number. Note
that for $k\in[i\ldots j]$, the value of $con_{j}(k)$ is completely
independent from $i$. Therefore, it can be equivalently defined as the value
that the update $(1,j,p)$ adds to index $k\leq j$. Consider an update
$(i,j,p)$ that was applied to $C$ before the query for the value $C[x]$. Let
$r_{j},q_{j}$ be the two unique non negative integers such that $j=q_{j}\cdot
p+r_{j}$ and $r_{j}\in[1\ldots p]$.

Note that if $r_{x}\leq r_{j}$, $con_{j}(r_{x})=\lceil\frac{j}{p}\rceil$, and
otherwise, $con_{j}(r_{x})=\lceil\frac{j}{p}\rceil-1$ That is due to the fact
that the leftmost step in the update $(1,j,p)$ is the
$\lceil\frac{j}{p}\rceil$’th step and it is of size $r_{j}$. Another property
of $con_{j}(k)$ is that for every two integers $q,k$ we have $con_{j}(q\cdot
p+k)=con_{j}(k)-q$. Putting the above observations together, we get
$con_{j}(x)=con_{j}(q_{x}\cdot p+r_{x})=con_{j}(r_{x})-q_{x}$. For $r_{x}\leq
r_{j}$, that is $con_{j}(x)=\lceil\frac{j}{p}\rceil-q_{x}$ and for
$r_{x}>r_{j}$ that is $con_{j}(x)=\lceil\frac{j}{p}\rceil-q_{x}-1$.

Let $U$ be the set of updates $(i,j,p)$ with $x\in[i\ldots j]$ that were
applied to $C$ prior to the query. The definition of $con_{j}(x)$ directly
implies that $C[x]=\Sigma_{(i,j,p)\in U}con_{j}(x)$. Let $U_{1}=\\{(i,j,p)\in
U\textit{ and }r_{x}\leq r_{j}\\}$ and $U_{2}=U\setminus U_{1}$. So we have
$C[x]=\Sigma_{(i,j,p)\in U_{1}}con_{j}(x)+\Sigma_{(i,j,p)\in
U_{2}}con_{j}(x)=\Sigma_{(i,j,p)\in U_{1}}(\lceil\frac{j}{p}\rceil-
q_{x})+\Sigma_{(i,j,p)\in U_{2}}(\lceil\frac{j}{p}\rceil-
q_{x}-1)=\Sigma_{(i,j,p)\in U}\lceil\frac{j}{p}\rceil-|U|\cdot q_{x}-|U_{2}|$.
One can easily confirm that $S=\Sigma_{(i,j,p)\in U}\lceil\frac{j}{p}\rceil$,
$C=|U|$ and $D=|U_{2}|$. ∎

With that, the proof of Theorem 2 is completed. Applying a decreasing stairs
update and querying for the value of $C[x]$ is done using a constant number of
2-dimensional and 3-dimensional range queries, so the time complexity for both
query and update is $O(\log^{3}(U))$. The space complexity is
$O(U\cdot\log^{2}(U))$ with $U$ being the amount of updates. The
initialization of the data structure requires initializing two empty dynamic
range queries data structures.

###  8.3 Variants

The following symmetric variant of decreasing stairs updates can also be
supported by a construction symmetric to ours:

######  Definition 104.

An increasing stairs update is given as $U=(i,j,p)$. Applying $U$ to a set of
indexed integers $C[1\ldots n]$ increases $C[a]$ for $a\in[i+(k-1)\cdot
p\ldots\min(i+k\cdot p-1,j)]$ by $k$ for every $1\leq
k\leq\lceil\frac{j-i+1}{k}\rceil$.

Increasing stairs updates are equivalent to decreasing stairs updates with
inverted indexes. Namely, let $C^{\prime}[1\ldots n]$ be an array with
$C^{\prime}[x]=C[n-x-1]$. Applying an increasing stairs update $u=(i,j,p)$ to
$C[i\ldots j]$ is equivalent to applying a decreasing stairs update
$((n-j-1,n-i-1,p)$ to $C^{\prime}$. Trivially, both types of queries can be
supported by maintaining two data structures, $I$ and $D$ for increasing and
decreasing stairs updates respectively, and reporting $C[i]=D[i]+I[i]$.

One can also consider a negative stairs update.

######  Definition 105.

An increasing (resp. decreasing) negative stairs update is given as
$U=(i,j,p)$. Applying $U$ to a set of indexed integers $C[1\ldots n]$
decreases $C[a]$ for $a\in[i+(k-1)\cdot p\ldots\min(i+k\cdot p-1,j)]$ (resp.
$a\in[max(j-k\cdot p+1,i)\ldots j-(k-1)\cdot p)]$ ) by $k$ for every $1\leq
k\leq\lceil\frac{j-i+1}{k}\rceil$.

In words, a negative stairs updates decreases the values of indexes on the
$k$th step by $k$ rather than increasing it by $k$. This kind of updates can
also be supported by maintaining two stairs data structures, $P$ and $N$, for
stairs updates and negative stairs updates respectively. Positive updates are
applied to $P$, and negative updates are applied to $N$ as if they were
positive. Upon a query index $i$, we output $C[i]=P[i]-N[i]$.

###  8.4 Updates reduction

We say that a set of updates $U=u_{1},u_{2}\ldots u_{t}$ can be reduced to
another set of updates $U^{\prime}$ if for every array $C$, applying all the
updates in $U$ on an array $C$ will result in the same modified array
$C^{\prime}$ as applying all the updates in $U^{\prime}$ on $C$.

In some settings, we can reduce a sequence of interval increment updates to a
small set of stairs updates and interval increment updates.

######  Lemma 106.

Let $p$ be an integer and $U=u_{1},u_{2}\ldots u_{|U|-1}$ be a sequence of
interval increment updates with $u_{t}=(i_{t},j_{t},1)$. If both $i_{t}$ and
$j_{t}$ are either fixed, or an arithmetic progression with difference $p$,
the sequence $U$ can be reduced to a set $U^{\prime}$ of interval increment
updates and stairs updates with stair width $|p|$ such that $|U^{\prime}|\in
O(1)$. $U^{\prime}$ can be evaluated in constant time.

Proof: we distinguish between the following cases

  1. 1.

Both $i_{t}$ and $j_{t}$ are fixed. In this case, $U$ can be reduced to a
single interval update $u^{\prime}=(i,j,|U|)$.

  2. 2.

$i$ is fixed and $j_{t}=j_{0}+t\cdot p$ with $p>0$. In this case, $U$ can be
reduced to two updates $U^{\prime}=\\{u^{\prime},s\\}$ with $s$ being a
decreasing stairs update $s=(j_{0},j_{|U|-1},p)$ and $u^{\prime}$ the interval
increment update $u^{\prime}=(i,j_{0},|U|)$. The case in which $p<0$ can be
handled the same way by considering $j_{t}$ in a reversed order.

  3. 3.

$i_{t}=i_{0}+t\cdot p$ with $p>0$ and $j$ is a constant. $U$ can be reduced to
two updates $U^{\prime}=\\{u^{\prime},s\\}$ with $s$ being an increasing
stairs update $s=(i_{0},i_{|U|-1},p)$ and the interval update
$u^{\prime}=(i_{|U|-1},j,|U|)$. The case where $p<0$ can be handled the same
way by considering $i_{t}$ in a reversed order.

  4. 4.

$i_{t}=i_{0}+t\cdot p$ and $j_{t}=j_{0}+t\cdot p$ be two arithmetic
progressions with $p>0$. $U$ can be reduced to a set of $3$ updates
$U^{\prime}=\\{s_{1},s_{2},u^{\prime}\\}$ with an increasing stairs update
$s_{1}=(i_{0},i_{|U|-1},p)$, an increasing negative stairs update
$s_{2}=(j_{0},j_{|U|-1},p)$ and an interval increment update
$u^{\prime}_{1}=(i_{|U|-1},j_{|U|-1},|U|)$.

It can be easily verified that in every case, applying the updates in
$U^{\prime}$ to a set of indexed integers is equivalent to applying $U$ to the
same set. For a visualization, See Figures 13 and 14. In every case, the set
$U^{\prime}$ contains at most three updates and can be evaluated in constant
time in a straightforward way given the representation of $i_{t}$ and $j_{t}$
as arithmetic progressions (or fixed values, depending on the case). ∎

$\displaystyle i$$\displaystyle j_{k}$$\displaystyle
p$+1+1+1+1+1$\displaystyle i$$\displaystyle j_{k}$$\displaystyle p$+3+4+1+2+5

Figure 13: An illustration of how applying all the interval increment updates
$U$ with $i_{t}$ being an arithmetic progression and a fixed $j_{t}$ has the
same effect as applying a stairs update (and a ’reminder’ interval increment
update)

$\displaystyle i_{0}$$\displaystyle j_{k}$$\displaystyle p$+1$\displaystyle
p$+3+4+1+2+1+1+1+3+2+1$\displaystyle i_{0}$$\displaystyle j_{k}$

Figure 14: An illustration of how applying a sequence of interval updates with
both ends being an arithmetic progression with difference $p$ is equivalent to
two stairs updates and an interval increment update. This set of updates can
be viewed as a ’sliding window’. The application of all the interval updates
can be represented as an increasing stairs update with the stairs
corresponding to the starting (left) indexes of the ’sliding window’ and a
negative increasing stairs update with the stairs corresponding to the ending
indexes of the windows.

## Acknowledgements

We warmly thank Eylon Yogev for assistance with the presentation and the
organization of the results presented in this manuscript.

## References

  * [1] Adjeroh, D., Bell, T., and Mukherjee, A. The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching.  Springer-Verlag, 2008.  ISBN 00387789081.
  * [2] Amir, A., Benson, G., and Farach, M. Let sleeping files lie: Pattern matching in z-compressed files.  Journal of Computer and System Sciences 52, 2 (1996), 299–307.
  * [3] Amir, A., and Boneh, I. Dynamic palindrome detection.  CoRR abs/1906.09732 (2019).
  * [4] Amir, A., and Boneh, I. Update query time trade-off for dynamic suffix arrays.  In Proc. 31st International Symposium on Algorithms and Computation (ISAAC) (2020).  to appear.
  * [5] Amir, A., Boneh, I., Charalampopoulos, P., and Kondratovsky, E. Repetition detection in a dynamic string.  In Proc. 27th Annual European Symposium on Algorithms (ESA) (September 2019), LIPIcs, pp. 5:1–5:18.
  * [6] Amir, A., Boneh, I., Charalampopoulos, P., and Kondratovsky, E. Repetition Detection in a Dynamic String.  In 27th Annual European Symposium on Algorithms (ESA 2019) (Dagstuhl, Germany, 2019), M. A. Bender, O. Svensson, and G. Herman, Eds., vol. 144 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 5:1–5:18.
  * [7] Apostolico, A. Fast gapped variants for lempel–ziv–welch compression.  Information and Computation 205, 7 (2007), 1012–1026.
  * [8] Apostolico, A., Breslauer, D., and Galil, Z. Optimal parallel algorithms for periods, palindromes and squares.  In Proc. 19th International Colloquium on Automata, Languages, and Programming (ICALP) (1992), vol. 623 of LNCS, Springer, pp. 296–307.
  * [9] Apostolico, A., Lewenstein, M., and Erdös, P. Parameterized matching with mismatches.  Journal of Discrete Algorithms 5, 1 (2007), 135–140.
  * [10] Baker, B. S. Parameterized pattern matching: Algorithms and applications.  Journal of Computer and System Sciences 52, 1 (1996), 28–42.
  * [11] Baker, B. S. Parameterized duplication in strings: Algorithms and an application to software maintenance.  SIAM Journal on Computing 26, 5 (1997), 1343–1362.
  * [12] Balkenhol, B., and Kurtz, S. Universal data compression based on the burrows-wheeler transformation: Theorey and practice.  IEEE Trans. on Computers 49, 10 (2000), 1043–1053.
  * [13] Benson, G. Tandem repeats finder: a program to analyze dna sequence.  Nucleic Acids Research 27, 2 (1999), 573–580.
  * [14] Bentley, J. L., and Friedman, J. H. Data structures for range searching.  ACM Computing Surveys (CSUR) 11, 4 (1979), 397–409.
  * [15] Charalampopoulos, P., Gawrychowski, P., and Pokorski, K. Dynamic longest common substring in polylogarithmic time.  In Proc. 47th International Colloquium on Automata, Languages and Programming (ICALP) (2020), vol. 168 of LIPIcs, pp. 27:1–27:19.
  * [16] Charalampopoulos, P., Kociumaka, T., and Mozes, S. Dynamic String Alignment.  In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020) (Dagstuhl, Germany, 2020), I. L. Gørtz and O. Weimann, Eds., vol. 161 of Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, pp. 9:1–9:13.
  * [17] Charalampopoulos, P., Kociumaka, T., and Wellnitz, P. Faster approximate pattern matching: A unified approach, 2020.
  * [18] Domaniç, N. O., and Preparata, F. P. A novel approach to the detection of genomic approximate tandem repeats in the levenshtein metric.  Journal of Computational Biology 14, 7 (2007), 873–891.
  * [19] Farach, M., and Thorup, M. String matching in lempel-ziv compressed strings.  Proc. 27th Annual ACM Symposium on the Theory of Computing (1995), 703–712.
  * [20] Fine, N. J., and Wilf, H. S. Uniqueness theorems for periodic functions.  Proceedings of the American Mathematical Society 16, 1 (1965), 109–114.
  * [21] Fischer, J. Inducing the lcp-array, 2011.
  * [22] Funakoshi, M., Nakashima, Y., Inenaga, S., Bannai, H., and Takeda, M. Faster queries for longest substring palindrome after block edit.  In 30th Combinatorial Pattern Matching conference CPM (2019), vol. 128 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 27:1–27:13.
  * [23] Gawrychowski, P., and Janczewski, W. Fully dynamic approximation of LIS in polylogarithmic time.  In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 (2021), S. Khuller and V. V. Williams, Eds., ACM, pp. 654–667.
  * [24] Gawrychowski, P., Karczmarz, A., Kociumaka, T., Lacki, J., and Sankowski, P. Optimal dynamic strings.  In Proceedings, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA (2018), pp. 1509–1528.
  * [25] Hazay, C., Lewenstein, M., and Sokol, D. Approximate parameterized matching.  In Proc. 12th Annual European Symposium on Algorithms (ESA 2004) (2004), pp. 414–425.
  * [26] Hohlweg, C., and Reutenauer, C. Lyndon words, permutations and trees.  Theoretical Computer Science 307, 1 (2003), 173–178.
  * [27] Kaplan, H., Porat, E., and Shafrir, N. Finding the position of the $k$-mismatch and approximate tandem repeats.  In Scandinavian Workshop on Algorithm Theory (SWAT06) (2006), pp. 90–101.
  * [28] Kociumaka, T., and Seddighin, S. Improved dynamic algorithms for longest increasing subsequence, 2021.
  * [29] Kucherov, G., and Sokol, D. Approximate tandem repeats.  In Encyclopedia of Algorithms. 2016, pp. 106–109.
  * [30] Landau, G., and Schmidt, J. An algorithm for approximate tandem repeats.  In Proc. 4th Annual Symp. on Combinatorial Pattern Matching, Lecture Notes in Computer Science, vol. 648. Springer-Verlag, 1993, pp. 120–133.
  * [31] Landau, G. M., Schmidt, J. P., and Sokol, D. An algorithm for approximate tandem repeats.  Journal of Computational Biology 8, 1 (2001), 1–18.
  * [32] Landau, G. M., and Vishkin, U. Efficient string matching with $k$ mismatches.  Theoretical Computer Science 43 (1986), 239–249.
  * [33] Landau, G. M., and Vishkin, U. Fast parallel and serial approximate string matching.  Journal of Algorithms 10, 2 (1989), 157–169.
  * [34] Lee, T., Na, J., and Park, K. On-line construction of parameterized suffix trees.  Information Processing Letters 111 (2011), 201–207.
  * [35] Loving, J., Scaduto, J. P., and Benson, G. An SIMD algorithm for wraparound tandem alignment.  In Proc. 13th International Symposium on Bioinformatics Research and Applications (ISBRA) (2017), pp. 140–149.
  * [36] Manber, U., and Myers, G. Suffix array: A new method for on-line string searches.  In Proc. 1st ACM-SIAM Symp. on Discrete Algorithms (SODA) (1990), pp. 319–327.
  * [37] Navarro, G., and Raffinot, M. A general practical approach to pattern matching over ziv-lempel compressed text.  In Proc. 10th Annual Symposium on Combinatorial Pattern Matching (CPM 99) (1999), pp. 14–36.  LNCS 1645.
  * [38] Nishimoto, T., I, T., Inenaga, S., Bannai, H., and Takeda, M. Fully Dynamic Data Structure for LCE Queries in Compressed Space.  In 41st Intl. Symp. Mathematical Foundations of Computer Science (MFCS) (2016), vol. 58 of LIPIcs, pp. 72:1–72:15.
  * [39] Nong, G., Zhang, S., and Chan, W. H. Linear suffix array construction by almost pure induced-sorting.  In 2009 Data Compression Conference (2009), pp. 193–202.
  * [40] Sadakane, K. A fast algorithm for making suffix arrays and for burrows-wheeler transformation.  In Proc. Data Compression Conference (DCC) (1998), pp. 129–138.
  * [41] Sokol, D., Benson, G., and Tojeira, J. Tandem repeats over the edit distance.  Bioinformatics 23, 2 (2007), 30–35.
  * [42] Weiner, P. Linear pattern matching algorithm.  Proc. 14 IEEE Symposium on Switching and Automata Theory (1973), 1–11.
  * [43] Welch, T. A. A technique for high-performance data compression.  IEEE Computer 17 (1984), 8–19.
  * [44] Wexler, Y., Yakhini, Z., Kashi, Y., and Geiger, D. Finding approximate tandem repeats in genomic sequences.  Journal of Computational Biology 12, 7 (2005), 928–942.
  * [45] Ziv, J., and Lempel, A. A universal algorithm for sequential data compression.  IEEE Trans. on Information Theory IT-23, 3 (1977), 337–343.
  * [46] Ziv, J., and Lempel, A. Compression of individual sequences via variable rate coding.  IEEE Trans. on Information Theory IT-24 (1978), 530–536.