# Dynamic Suffix Array with Sub-linear update time and Poly-logarithmic Lookup
Time

Amihood Amir Itai Boneh Bar-Ilan University Bar-Ilan University and Georgia
Tech Department of Computer Science, Bar-Ilan University, Ramat-Gan 52900,
Israel, +972 3 531-8770<EMAIL_ADDRESS>of Computer Science, Bar-
Ilan University, Ramat Gan, Israel, email<EMAIL_ADDRESS>
###### Abstract

The suffix array $SA_{S}[1\ldots n]$ of an $n$-length string $S$ is a
lexicographically sorted array of the suffixes of $S$. The suffix array is one
of the most well known and widely used data structures in string algorithms.
We present a data structure for maintaining a representation of the suffix
array of a dynamic string which undergoes symbol substitutions, deletions, and
insertions.

For every string manipulation, our data structure can be updated in
$\tilde{\mathcal{O}}(n^{\frac{2}{3}})$ time with $n$ being the current length
of the string. For an input query $i\in[1\ldots n]$, our data structure
reports $SA_{S}[i]$ in $O(\log^{5}(n))$ time.

We also present a faster data structure, with $\tilde{\mathcal{O}}(\sqrt{n})$
update time, for maintaining the Inverted Suffix Array of a dynamic string
undergoing symbol substitutions updates. For an input query $i\in[1\ldots n]$,
our data structure reports the $i$’th entry in the inverted suffix array in
$O(\log^{4}(n))$ time.

Our data structures can be used to obtain sub-linear dynamic algorithms for
several classical string problems for which efficient dynamic solutions were
not previously known.

##  1 Introduction

Recently, there has been a growing interest in dynamic strings algorithms.
Many classical stringology problems have been lately investigated in dynamic
settings. Perhaps the most natural problem of stringology is the one of
constructing an index for a given string. That is, preprocessing a string $S$
in order to obtain a data structure that given an input word $p$, outputs the
set $occ$ of indexes in $S$ in which the word $p$ occurs. In the dynamic
settings, we wish to maintain an index for a string that undergoes edit
operations (substitution, deletion, or insertion of a single symbol in any
location in the text). The current state of the art for dynamic indexing is
the data structure of [24] that requires $O(\log^{2}(n))$ time per update and
supports $O(p+\log^{2}(n)+|occ|)$ time queries.

In the Longest Common Factor problem, we are given two strings $S$ and $T$. We
are interested in finding the largest words that is a substring of both $S$
and $T$. Charalampopoulos et al. [15] show how to maintain the LCF of two
dynamic strings $S$ and $T$ that are going through edit operation updates with
polylogarithmic time per update. In the Longest Increasing Subsequence
problem, we are given an input string $S[1\ldots n]$ that consists of numbers.
We are interested in finding the longest increasing sequence of indexes
${i_{1},i_{2}\ldots i_{x}}\subseteq[1\ldots n]$ such that
$S[i_{j}]<S[i_{j+1}]$ for every $j\in[1\ldots x-1]$. Gawrychowski et al. [23]
provided an algorithm for maintaining an approximation of the LIS of a dynamic
string in polylogarithmic time per update. Kociumaka and Seddighin [28]
provided an algorithm for maintaining the exact LIS of a dynamic string with
polynomial sublinear time per update. In addition to the above, the problems
of finding the longest palindrome substring in a text [3, 22], finding all the
runs in a text [5], approximated pattern matching [17], and computing the edit
distance between two strings [16] have all been recently investigated in
dynamic settings.

The natural interest in dynamic strings algorithms grows from the fact that
the biggest digital library in the world - the web - is constantly changing,
as well as from the fact that other big digital libraries - genomes and
astrophysical data, are also subject to change through mutation and time,
respectively.

The suffix tree [42] and suffix array [36] have been, arguably, the most
powerful and heavily used tools in Stringology. The suffix tree of string $S$
is a compressed trie of all suffixes of $S$, and the suffix array of $S$
corresponds to a pre-order traversal of all the leaves of the suffix tree of
$S$. The natural application of the suffix tree is for indexing, but it has
been used for many purposes. An incomplete list includes approximate matching
[32, 33], parameterized matching [10, 11, 9, 25, 34], efficient compression
[45, 46, 2, 43, 19, 40, 37, 12, 7, 1], finding syntactic regularities in
strings [8, 30, 13, 31, 26, 44, 27, 18, 41, 29, 35], and much more.

It was not until recently that an algorithm for maintaining the suffix tree or
suffix array of a dynamically changing text had been sought. The difficulty is
that even a single change in the text may cause a change in linear number of
entries in the suffix array. Thus, although a dynamic suffix array algorithm
would be extremely useful to automatically adapt many static pattern matching
algorithms to a dynamic setting, other techniques had to be sought.

The key to most recent efficient dynamic solutions that appeared in the
Stringology literature is renaming. However, renaming is not a panacea for
dynamic algorithms to all the problems that the suffix tree or array solved in
the static setting. Perhaps the key property of the suffix array is that the
suffixes are sorted lexicographically. The powerful renaming and locally
persistent parsing techniques developed thus far do not maintain lexicographic
ordering. It is, thus, no surprise that problems like maintaining the Burrows-
Wheeler transform, or finding the Lyndon root of a substring, do not hitherto
have an efficient dynamic version.

The current state of the art for maintaining the suffix array of a dynamic
text is the flexible data structure of Amir and Boneh [4]. For every parameter
$k\in[1\ldots n]$, they provide a data structure with $\tilde{\mathcal{O}}(k)$
update time supporting look up queries to $SA[i]$ in
$\tilde{\mathcal{O}}(\frac{n}{k})$ time.

###  1.1 Our Contribution

We enhance the data structure of Amir and Boneh [4] to obtain the following.

  1. 1.

A data structure for maintaining the suffix array of a dynamic string in
$\tilde{\mathcal{O}}(n^{\frac{2}{3}})$ time per text update with
$O(\log^{5}(n))$ time for a look up query $SA[i]$. This data structure
supports symbol substitution, symbol insertion and symbol deletion updates.

  2. 2.

A data structure for maintaining the inverted suffix array of a dynamic string
in $\tilde{\mathcal{O}}(\sqrt{n})$ time per text update with $O(\log^{4}(n))$
time for a look up query $SA[i]$. This data structure only supports symbol
substitution updates.

Both data structures use $\tilde{\mathcal{O}}(n)$ space. Note that our data
structures maintain the sublinear polynomial update time of [4], and
exponentially improve the query time from polynomial to polylogarithmic.
Additionally, our data structure for dynamic suffix array can be used as a
black box, alongside previously existing results, to obtain the following.

  1. 1.

A dynamic text $S[1\ldots n]$ can be maintained with
$\tilde{\mathcal{O}}(n^{\frac{2}{3}})$ time per edit operation update to
support random access queries to $BWT[i]$, the burrows wheeler transform of
$S$, in polylogarithmic time.

  2. 2.

A dynamic text $S[1\ldots n]$ can be maintained with
$\tilde{\mathcal{O}}(n^{\frac{2}{3}})$ time per edit operation update to
enable random access queries to the $LCP$ array of $S$ in polylogarithmic
time.

  3. 3.

A dynamic text $S[1\ldots n]$ can be maintained with
$\tilde{\mathcal{O}}(n^{\frac{2}{3}})$ time per edit operation update to
enable a simulation of the suffix tree of $S$ with polylogarithmic time for
traversing a suffix tree edge.

In [4], summarized in Section 6, the above results are presented with a
polynomial query time, rather then polylogarithmic. Replacing the data
structure of [4] with ours yields the above. We refer the interested reader to
[4] for an overview of how a dynamic suffix array is utilized to achieve these
results.

###  1.2 Technical Overview

Dynamic Inverse Suffix Array Similarly to [4], we partition the suffixes of
the the dynamic string $S[1\ldots n]$ into clusters. Every cluster $C$
corresponds to a word $w_{C}$ with length $|w_{C}|=\sqrt{n}$. The cluster $C$
contains all the suffixes starting with the prefix $w_{C}$. We say that two
suffixes are close if they are located within the same cluster, and far
otherwise. It is shown in [4] that these clusters can be maintained in
$\tilde{\mathcal{O}}(\sqrt{n})$ time when a substitution update is applied to
$S$.

Given a query $i$ for $iSA[i]$, we are interested in finding the
lexicographical rank of $S[i\ldots n]$ among the suffixes of $S$.
Equivalently, we want to count the number of suffixes of $S[1\ldots n]$ that
are lexicographically smaller than $S[i\ldots n]$. The inverse suffix array
algorithm of [4] counts the number of suffixes far from $S[i\ldots n]$ that
are smaller than $S[i\ldots n]$. The bottleneck that causes for the polynomial
query time in [4] is counting the number of close suffixes that are smaller
than $S[i\ldots n]$. This task can be equivalently described as evaluating the
lexicographical rank of $S[i\ldots n]$ within the suffixes in its cluster.

In order to overcome this bottleneck, we wish to maintain an ’array’
$R[1\ldots n]$. For every suffix $S[i\ldots n]$, $R[i]$ stores the rank of
$S[i\ldots n]$ within the suffixes in its cluster. In order to update $R$ in
sublinear time, we provide a deep analysis of the nature in which the ranks in
$R$ change is as a result of a substitution update. The conclusion of our
analysis is that while $R$ may require updates in $\Omega(n)$ entries as a
result in a single substitution, these updates can be compactly described as a
sequence of $O(\sqrt{n})$ special updates called stairs updates.

######  Definition 1.

A decreasing stairs update (See Figure 2) is denoted by $S=(i,j,p)$. Applying
$S$ to $R$ increases the values stored in $R[i\ldots j]$ as follows: the
rightmost $p$ indexes $R[j-p+1\ldots j]$ are increased by $1$, the $p$ indexes
to their left are increased by $2$, and so on until we finally exceed
$R[i\ldots j]$.

Formally, for every $t\in[1\ldots\lceil\frac{j-i+1}{p}\rceil]$, the counters
$R[a]$ with $a\in[max(j-t\cdot p+1,i)\ldots j-(t-1)\cdot p]$ are increased by
$t$.

We show how to obtain the sequence of $O(\sqrt{n})$ stairs updates that
represent the changes to $R$ in $\tilde{\mathcal{O}}(\sqrt{n})$ time. We then
provide a data structure that maintains an ordered set of integers that is
applied a sequence of stairs updates. The utility of provided by our data
structure for stairs updates is described by Theorem 2.

######  Theorem 2.

There is a data structure for maintaining an indexed set of integers $R$ to
support both applying a stairs update to $R$ and look-up queries $R[i]$ in
$O(\log^{3}(U))$ time, provided that all the updates $(i,j,p)$ have the same
value of $p$. $U$ is the overall amount of updates. The data structure
consumes $O(U\log^{2}(U))$ space. Initializing the data structure (all
counters are set to $0$) takes $O(1)$ time.

The restriction that every stair update that is applied to the ranks has the
same width $p$ does not necessarily hold in our dynamic algorithm. It may be
the case that the stairs updates within the sequence have various step widths,
or that the stairs updates applied in the most recent update have different
step width from the updates that were applied in previous update. This denies
us from using our data structure for stairs update in a straight forward
manner to maintain $R$.

In order to solve that problem, we identify a unique property of the stairs
updates that need to be applied to $R$.

######  Observation 3.

Every stairs update $(i,j,p)$ that is applied to $R$ corresponds to a run
$S[i\ldots j]$ in $S$ with period $p$.

Observation 3 allows us to exploit existing insights on the structure of runs
within a string to bound the number of different values of $p$ for which a
stairs update with step width $p$ was applied to an index $i$ in $R$.
Specifically, we show that there are $O(\log(n))$ such values of $p$. With
this property, our problem can be reduced to maintaining a sequence
$\\{St_{1},St_{2}\ldots St_{n}\\}$ of restricted stairs updates data structure
described in Theorem 2. Every stairs update data structure $St_{p}$ is
responsible for updates with a step width $p$. When we wish to evaluate
$R[i]$, we sum the values stored in $St_{p}$ over the $p$ values such that
$St_{p}[i]$ was affected by a stairs update. Since there are $O(\log(n))$ such
values, the query time remains polylogarithmic.

Dynamic Suffix Array As in our solution for inverse suffix arrays, we build
upon the data structure presented in [4]. For an integer parameter $k$, the
dynamic data structure of [4] provides the following utility.

######  Fact 4.

A query $i$ for $SA_{S}[i]$ of a dynamic $S$ can be reduced to a Close Suffix
Selection query (defined below) in $O(\log^{2}(n))$ time. The data structure
for executing this reduction can be maintained in $O(k)$ time per edit
operation update.

Close Suffixes Select
Given a subword of size $k$ of $S$ represented by its starting index
$i\in[1\ldots n-k+1]$ and a rank $r$, return the suffix $S[i\ldots n]$ with
lexicographic rank $r$ among the suffixes starting with $S[i\ldots i+k-1]$

In Section 4, we prove the following:

######  Theorem 5.

Given a dynamic text $S[1\ldots n]$, there is a data structure that support
close suffixes selection queries in $O(\log^{5}(n))$ time. The data structure
can be maintained in $\tilde{\mathcal{O}}((\frac{n}{k})^{2}+k)$ time when an
edit operation is applied to $S$. The data structure uses
$\tilde{\mathcal{O}}(n+(\frac{n}{k})^{2})$ space.

By setting $k=n^{\frac{2}{3}}$ and applying the above reduction, we obtain the
following:

######  Theorem 6.

For a dynamic string $S[1\ldots n]$, there is a data structure that supports
look up queries to $SA_{S}[i]$ in $O(\log^{5}(n))$ time. When an edit
operation update is applied to $S$, the data structure can be maintained in
$\tilde{\mathcal{O}}(n^{\frac{2}{3}})$ time. The data structure uses
$\tilde{\mathcal{O}}(n)$ space.

We present the main idea for proving Theorem 23. Let $w$ be a word of size
$t=\frac{k}{2}$. By exploiting periodic structures in strings, we can
represent all the occurrences of a $w$ in $S[1\ldots n]$ with $O(\frac{n}{k})$
arithmetic progressions. We denote this compact set of arithmetic progressions
representing the occurrences of $w$ as $POR_{w}$. The data structure of [4]
allows the evaluation of $POR_{w}$ from an index $i$ representing a starting
index of $w$ in $\tilde{\mathcal{O}}(|POR_{w}|)$ time. We denote the explicit
set of occurrences of $w$ in $S$ as $Occ_{w}$. We denote as
$A_{w}[1\ldots|Occ_{w}|]$ the array consisting of the starting indexes of
occurrences of $w$ sorted by lexicographic order of the suffixes starting in
these indexes. While the size of $POR_{w}$ is bounded by $O(\frac{n}{k})$, the
size of $A_{w}$ may be $\Omega(n)$. Note that a Close suffix selection query
is equivalent to a random access query in $A_{w}$.

Let $C=(a,b,p)\in POR_{w}$ be an arithmetic progression in the representation
of the occurrences of $w$. We denote the size of the cluster as
$|C|=\frac{b-a}{p}+1$. The arithmetic progression $C$ corresponds to
occurrences of $w$ starting in $a,a+p,a+2\cdot p\ldots a+|C|\cdot p=b$. We say
that $C$ implies these occurrences of $w$. We define the following properties
of clusters and of occurrences implied by clusters.

######  Definition 7.

Let $w_{i}=S[a+i\cdot p\ldots a+i\cdot p+t-1]$ be an occurrence implied by $C$
of $w$. The period rank of $w_{t}$ is defined to be $r_{p}(w_{t})=|C|-i$.

######  Definition 8 (Cluster Head, Cluster Tail, Increasing and Decreasing
Clusters).

Let $w_{|C|}=[b\ldots b+t-1]$ be the rightmost occurrence of $w$ represented
by $C$ (with respect to starting index). Let $w_{s}=w[e-p+1\ldots e]$ be the
suffix of size $p$ of $w$. We call the suffix $S[b+t\ldots n]$ the tail of $C$
denoted as $Tail(C)$. We call $C$ an increasing cluster if
$Tail(C)>_{L}w_{s}$, or a decreasing cluster if $Tail(C)<_{L}w_{s}$.

See Figure 1 for an example of a cluster and its properties. In Section 7, we
prove that $A_{w}$ has the following structure (derived from Lemma 74 and
Lemma 75):

$A_{w}$ can be described as a concatenation
$A_{w}=D[1\ldots|D|],I[1\ldots|I|]$ with $D$ being the sub array containing
the set of occurrences implied by decreasing clusters, and $I$ being the set
of occurrences implied by increasing clusters.

$D$ can be written as the concatenation $D=D_{0},D_{1}\ldots D_{m-1},D_{m}$.
$m$ is the maximal period rank of an occurrence in a decreasing cluster. For
every $r\in[0\ldots m]$ , $D_{r}$ contains the occurrences $w^{\prime}$ from
decreasing clusters with $r_{p}(w^{\prime})=r$ sorted by lexicographic order
of the tails of their clusters.

Similarly, $I=I_{t},I_{t-1}\ldots I_{1},I_{0}$. $t$ is the maximal period rank
of an occurrence in an increasing cluster. For every $r\in[0\ldots t]$ ,
$I_{r}$ contains the occurrences $s$ from increasing clusters with
$r_{p}(s)=r$ sorted by lexicographic order of the tails of their clusters (See
Figure 8).

Let $w=S[s\ldots e]$ be a subword of $S$. Let $l$ and $r$ be two non-negative
integers.

######  Definition 9.

An occurrence $w_{1}=S[s_{1}\ldots e_{1}]$ of $w$ is an $(l,r)$-extendable
occurrence of $w$ if $lcs(s-1,s_{1}-1)\geq l$ and $lcp(e+1,e_{1}+1)\geq r$. We
define the array $A^{(l,r)}_{w}$ as the lexicographically sorted array of
suffixes of $S$ starting with an $(l,r)$-extendable occurrence of $w$.

It is easy to see that given a word $w^{c}=S[s-l\ldots e+r]$ containing $w$,
an occurrence of $w^{c}$ in index $i$ is equivalent to an $(l,r)$-extendable
occurrence of $w$ in $i+l$. Therefore, $A_{w^{c}}[i]=A^{(l,r)}_{w}[i]-l$ for
every $i\in[1\ldots|A_{w^{c}}|]$. We present the following problem:

Extension Restricting Selection
Preprocess: A word $w=S[s\ldots e]$ and $POR_{w}$ Query: upon input $l,r,i$.
Report $A^{(l,r)}_{w}[i]$

In Section 7, we prove the following:

######  Theorem 10.

If $LCE$ queries can be evaluated in $O(\log(n))$ time, 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 Selection queries in $O(\log^{5}(n))$ time. The data structure
uses $\tilde{\mathcal{O}}(|POR_{w}|)$ space.

LCE queries are formally defined in Section 2. Existing results in dynamic
stringology can be used in a straight forward manner to enable $O(\log(n))$
LCE queries in dynamic settings.

Constructing the data structure described in Theorem 28 is the most
technically involved part in the construction of our dynamic suffix array data
structure. It is achieved by exploiting the characterization of the structure
of $A_{w}$. Our insights on the structure of $A_{w}$ allow us to reduce an
Extension Restricting Selection query to a small set of multidimensional range
queries.

With the data structure of Theorem 28, a dynamic data structure for Close
Suffix selection queries can be constructed as follows. We initialize a data
structure for supporting dynamic $LCE$ queries on $S$ by employing Lemma 11.
We also initialize the dynamic data structure of Fact 4 for obtaining periodic
occurrences representations and reducing suffix array queries to close
selection queries. Let $t=\lfloor\frac{k}{2}\rfloor$. We partition $S$ into
words of size $t$ starting in indexes $i=0\bmod t$. For every word
$w_{x}=S[x\cdot t\ldots(x+1)\cdot t-1]$ for
$x\in[0\ldots\lfloor\frac{n}{t}\rfloor]$, we obtain $POR_{w_{x}}$ in
$\tilde{\mathcal{O}}(\frac{n}{t})$ time. We preprocess $POR_{w_{x}}$ for
Extension Restricting Selection queries using Theorem 28. We keep an array
$ERSQ[1\ldots\lfloor\frac{n}{t}\rfloor]$ with $ERSQ[x]$ containing a pointer
to the Extension Restricting Selection queries data structure of $w_{x}$.

Upon an edit operation update, we update the data structures of Fact 4. We
then partition the updated $S$ in the same manner as in the initialization
step. Note that the words in the partition may change, as the size of $S$ may
change due to an insertion or a deletion update, and $k$ may be a function of
$|S|=n$. For every word $w_{x}$ in the updated partition, we extract
$POR_{w_{x}}$ and evaluate the extension restricting selection queries data
structures for every word $w_{x}$ from scratch. We also construct the array
$ERSQ$ from scratch as in the initialization step.

Upon a Close Suffix Selection query $(i,r)$, the word
$w_{\lceil\frac{i}{t}\rceil}$ is completely contained within $w=S[i\ldots
i+k-1]$. Let $L$ be the distance between the starting indexes of
$w_{\lceil\frac{i}{t}\rceil}$ and $w$ and let $R$ be the distance between the
ending indexes. We execute an Extension Restricting Selection query $(L,R,r)$
on the Extension Restricting Selection queries data structure of
$w_{\lceil\frac{i}{t}\rceil}$. Let the output of the query be $z$. We return
$z-L$ .

Correctness: A Close Suffix Selection query $(i,r)$ is equivalent to reporting
$A_{w}[r]$. Denote the indexes of $w_{\lceil\frac{i}{t}\rceil}=S[s\ldots e]$.
The word $w=S[i\ldots i+k-1]$ can be written as $w=S[s-L,e+R]$. Therefore,
$A_{w}[r]=A^{(L,R)}_{w_{\lceil\frac{i}{t}\rceil}}[r]-L$.

Preprocessing time: The preprocessing times of the $LCE$ data structure and
the periodic occurrences data structure are both bounded by
$\tilde{\mathcal{O}}(n)$. The remaining operations are, in fact, an initial
update. The complexity analysis for these is provided below.

Update time: Evaluating the partition can be executed in $O(\frac{n}{k})$ time
in a straightforward manner. There are $\frac{n}{t}\in O(\frac{n}{k})$ words
in our partition. For every word $w$, we find $POR_{w}$ in
$\tilde{\mathcal{O}}(\frac{n}{k})$ time. Since $|w|=\frac{k}{2}$, we have
$|POR_{w}|\in O(\frac{n}{k})$. So constructing the Extension Restricting
Selection data structure from $POR_{w}$ takes
$\tilde{\mathcal{O}}(\frac{n}{k})$. The update time for the $LCE$ data
structure is polylogarithmic and the update time for the periodic occurrences
representation data structure is $\tilde{\mathcal{O}}(k)$. The overall update
complexity is dominated by $\tilde{\mathcal{O}}((\frac{n}{k})^{2}+k)$.

Space: The space consumed by the Extension Restricting Selection data
structures is bounded by $\tilde{\mathcal{O}}((\frac{n}{k})^{2})$. The space
consumed by the array $ERSQ$ is bounded by $O(\frac{n}{k})$. The space
consumed by the data structure for periodic occurrences representation is
bounded by $O(n)$. The space consumed by the $LCE$ data structure is bounded
by $\tilde{\mathcal{O}}(n)$. The overall space complexity is bounded by
$\tilde{\mathcal{O}}(n+(\frac{n}{k})^{2})$.

Query time: The query consists of a constant number of basic arithmetic
operations, a single array lookup and a single Extension Restricting Selection
query. The query time is dominated by $O(\log^{5}(n))$. ∎

###  1.3 Roadmap

This paper is organized as follows: Section 2 gives basic definitions and
terminology. Section 3 provides an overview of [4], and presents the
bottleneck in the complexity of the algorithms presented there. This
identifies the difficulty that the current paper solves. In Section 4 we
present a static data structure problem, and show that, surprisingly, an
efficient data structure for solving this problem, enables us to construct an
efficient dynamic suffix array data structure. We provide an efficient
solution for this problem in Section 7. For dynamic inverted suffix array
queries, our results appear in Section 5. Section 6 provides some
complementary proofs for the result of Section 5. Section 8 provides two data
structures that are required for the construction of Section 5.

##  2 Preliminaries

###  2.1 Strings

Let $S=S[1]S[2]\ldots S[n]$ be a string (or a word) of length $|S|=n$ over an
ordered alphabet $\Sigma$ of size $|\Sigma|=\sigma$. By $\varepsilon$ we
denote an empty string. For two positions $i$ and $j$ in $S$, we denote by
$S[i\ldots j]=S[i]\ldots S[j]$ the factor (sometimes called substring) of $S$
that starts at position $i$ and ends at position $j$ (it equals $\varepsilon$
if $j<i$). We recall that a prefix of $S$ is a factor that starts at position
$1$ ($S[1\ldots j]$) and a suffix is a factor that ends at position $n$
($S[i\ldots n]$). The prefix ending in index $i$ is denoted as $S_{i}$ and the
suffix starting in index $i$ is denoted as $S^{i}$.

An integer $p$ is a period of $S$ if $S[i]=S[i+p]$ for every $i\in[1\ldots
n-p]$. $p$ is called the period of $S$ if it is the minimal period of $S$. We
denote the period of a string $S$ as $per(S)$. If $per(S)<\frac{|S|}{2}$, we
say that $S$ is periodic. A substring $R=S[i\ldots j]$ of $S$ is called a run
if it is periodic with period $p$, and every substring of $S$ containing $R$
does not have a period $p$. Equivalently, $R$ is a run if it is periodic with
period $p$, and $S[i-1]\neq S[i-1+p]$ and $S[j+1]\neq S[j+1-p]$. If $R$ is a
prefix (resp. suffix) of $S$, the first (resp. second) constraint is not
required.

Let $w[1\ldots m]$ be a string. We say that $w$ occurs in position
$i\in[1\ldots n-m+1]$ in $S$ if $S[i+j-1]=w[j]$ for every $j\in[1\ldots m]$.
Every substring $S[i\ldots i+m-1]=w$ is an occurrence of $w$ starting in index
$i$.

The longest common prefix of two strings $S[1\ldots n],T[1\ldots m]$ , denoted
as $LCP(S,T)$, is the maximal integer $l\in[1\ldots\min(n,m)]$ such that
$S[1\ldots l]=T[1\ldots l]$. The longest common suffix of $S$ and $T$, denoted
as $LCS(S,T)$, is the maximal integer $l\in[1\ldots\min(n,m)]$ such that
$S[n-l+1\ldots n]=T[m-l+1\ldots m]$.

Given a string $S$, a Longest Common Extension (often shortened to $LCE$) data
structure for $S$ supports the two following queries:

  1. 1.

$LCP(i,j)$ \- return the longest common prefix of $S[i\ldots n]$ and
$S[j\ldots n]$.

  2. 2.

$LCS(i,j)$ \- return the longest common suffix of $S[1\ldots i]$ and
$S[1\ldots j]$.

The results of ([24]) or of ([38]) can be applied to obtain the following:

######  Lemma 11.

There is a deterministic (res. randomized) data structure for maintaining a
dynamic string with $O(\log(n)\log^{*}(n))$ (resp. $O(\log(n))$ excepted) time
per edit operation (deletion, insertion, or substitution of a symbol) so that
an $LCE$ query can be answered in $O(\log(n)\log^{*}(n))$ (resp. $O(\log(n))$
expected) time. The data structure uses $\tilde{\mathcal{O}}(n)$ space.

Remark: Throughout the paper, we use the randomized variant of Lemma 11. Thus,
we refer to the application of an $LCE$ query as an $O(\log(n))$ time
operation. Every such reference to Lemma 11 can be made deterministic by
applying the deterministic variant of the lemma with the cost of an
$O(\log^{*}(n))$ multiplicative slowdown.

We point out that other than $LCE$ queries, the algorithms presented in this
paper do not use randomization. Therefore, our results can be derandomized by
adding a multiplicative $\log^{*}(n)$ factor to the complexity of an $LCE$
query.
Let $S[1\ldots n]$ and $T[1\ldots m]$ be two strings over an ordered alphabet
$\Sigma$. $S$ is lexicographically smaller than $T$, denoted as $S<_{L}T$, if
$S[LCP(S,T)+1]<T[LCP(S,T)+1]$. In the case in which $LCP(S,T)=\min(|S|,|T|)$,
$S<_{L}T$ if $|S|<|T|$. Note that given two indexes $i$ and $j$ representing
two suffixes of a string $S$, Lemma 11 enables to lexicographically compare
$S^{i}$ and $S^{j}$ in $O(\log(n))$ time.
The suffix array $SA_{S}$ is an array of size $n$ containing the suffixes of
$S$ sorted lexicographically. A suffix $S[i\ldots n]$ is represented in
$SA_{S}$ by its starting index $i$, so the size of $SA_{S}$ is linear. The
Inverse Suffix Array $iSA_{S}$ is the inverse permutation of the suffix array.
Namely, $iSA_{S}[SA_{S}[x]]=x$ for every $x\in[1\ldots n]$.
In this paper, we handle a dynamic string that is undergoing substitution,
deletion, and insertion updates. A substitution update is given as a pair
$(i,\sigma)$. Applying the update $(i,\sigma)$ to $S$ sets $S[i]=\sigma$ and
does not affect any other index in $S$. We always assume that the applied
substitution update is not trivial. Namely, $S[i]\neq\sigma$ prior to the
substitution. An insertion update is also given as a pair $(i,\sigma)$.
Applying the insertion $(i,\sigma)$ to $S$ results in a new text
$S^{\prime}=S[1\ldots i]\sigma S[i+1\ldots n]$. A deletion update is given as
an index $i$, Applying a deletion in index $i$ to $S$ results in a new text
$S^{\prime}=S[1\ldots i-1]S[i+1\ldots n]$. We collectively refer to
substitution updates, insertion updates and deletion updates as edit updates
or edit operations.

###  2.2 Periodic Structures

To achieve efficiency, we often need to simultaneously process the set of
occurrences of a word $w$ in $S$. To that end we exploit the periodic
structure of words with numerous occurrences within $S$. The periodicity lemma
([20]) states the following.

######  Lemma 12.

If a string $S[1\ldots n]$ has a period $p$ and a period $q$ such that $n\geq
p+q-gcd(p,q)$, then $gcd(p,q)$ is also a period of $S$.

The following is a basic observation regarding the occurrences of a word
within $S$.

######  Observation 13.

Given a word $w$ with size $|w|=x$ and period $p$, starting in index $i$ in
$S$, let $j$ be the index closest to $i$ that is also a starting index of an
occurrence of $w$ in $S$. Either $|j-i|=p$ or $|j-i|\geq\frac{x}{2}$.

With Observation 13, we are ready to introduce the periodic occurrences
representation.

######  Fact 14.

The set of occurrences of a word $w$ having length $x$ and with period $p$ in
a string $S[1\ldots n]$ can be represented by $O(\frac{n}{x})$ arithmetic
progressions (often referred to as clusters) of the form $C=(a,b,p)$. The
cluster $C=(a,b,p)$ represents a set of occurrences of $w$ starting in indexes
$i_{t}=a+p\cdot t$ with $t\in[0..\frac{b-a}{p}]$. The size of a cluster,
denoted as $|C|=\frac{b-a}{p}+1$ is the number of occurrences represented by
$C$. Every cluster $C$ is associated with a run $R_{C}$ in $S$ with period
$p$. The occurrences represented by $C$ are all the occurrences of $w$
contained within $R_{C}$. It follows that every cluster is locally maximal, in
the sense that there are no occurrences of $w$ starting in $a-p$ or in $b+p$.

We call the representation of the occurrences of $w$ described in Fact 14 the
periodic occurrences representation of $w$.

######  Lemma 15.

For every parameter $x\in[1\ldots n]$, there is a data structure that, given
input integer $i$, outputs the periodic occurrences representation of
$S[i\ldots i+x-1]$ in a dynamic text $S[1\ldots n]$ in
$\tilde{\mathcal{O}}(\frac{n}{x})$ time. This data structure can be maintained
in $\tilde{\mathcal{O}}(x)$ time after an edit operation update is applied to
$S[1\ldots n]$.

Lemma 3 of [4] and the discussion following Observation 1 there, serve as a
proof for Lemma 15. Specifically, the discussion following Observation 1
presents a method for obtaining the periodic occurrences representation of $w$
in $\tilde{\mathcal{O}}(\frac{n}{x})$ time using, what they called, the
$k$-Words tree data structure. Lemma 3 ensures that the $k$-Words tree can be
maintained over edit operations updates in $\tilde{\mathcal{O}}(x)$ time.
While the lemma in [4] refers to a dynamic text undergoing substitution
updates, it can be easily generalized to edit operations.

###  2.3 Dynamic multidimensional range queries

Dynamic multidimensional range queries is an algorithmic tool enabling the
maintenance of a set of $d$-dimensional points. A data structure for
$d$-dimensional range queries supports queries concerning the points within an
input $d$-dimensional range. A $d$-dimensional point is given by the values of
its $d$ coordinates. A $d$-dimensional range $R$ is given by a set of $d$
ranges $R=[X_{1}\ldots Y_{1}]\times[X_{2}\ldots
Y_{2}]\times\cdots\times[X_{d}\ldots Y_{d}]$. The point $p=(x_{1},x_{2}\ldots
x_{d})$ is in the range $R$ ($p\in R$) if $X_{i}\leq x_{i}\leq Y_{i}$ for
every $i\in[1\ldots d]$. Every point $p$ is assigned a numeric value $v(p)$.
The result below can be achieved by using the range tree data structure [14].

######  Fact 16.

There is a data structure for maintaining a set $D$ of $d$-dimensional points
and supports the following queries:

  1. 1.

Add a new point $p=(x_{1},x_{2},\ldots x_{d})$ with value $v(p)=v$ to $D$.

  2. 2.

Remove an existing point $p=(x_{1},x_{2},\ldots x_{d})$ from $D$.

  3. 3.

$COUNT(R)$ Given a $d$-dimensional range $R=[X_{1}\ldots
Y_{1}]\times[X_{2}\ldots Y_{2}]\ldots[X_{d}\ldots Y_{d}]$, report the number
of points in $D\cap R$.

  4. 4.

$SUM(R)$: Given a $d$-dimensional range $R=[X_{1}\ldots
Y_{1}]\times[X_{2}\ldots Y_{2}]\ldots[X_{d}\ldots Y_{d}]$, report the sum of
$v(p)$ taken over the points in $D\cap R$. The sum of an empty set is defined
to be 0.

  5. 5.

$REPORT(R)$: Given a $d$-dimensional range $R=[X_{1}\ldots
Y_{1}]\times[X_{2}\ldots Y_{2}]\ldots[X_{d}\ldots Y_{d}]$, return all the
points in $D\cap R$.

Queries 1 - 4 can be supported in $O(\log^{d}(n))$ and range report queries
can be supported in $O(\log^{d}(n)+k)$ with $k$ being the amount of reported
points and $n$ being the number of points in $D$. The data structure consumes
$O(\log^{d-1}(n))$ space.

##  3 Close Suffix Selection and Close Suffix Rank

Our algorithm improves the results of [4]. For self-containment, this section
provides an overview of the terminology, techniques, and results of [4] that
are relevant to our work. This section also identifies the sub-tasks that need
to be efficiently implemented in order to improve the previous work.

###  3.1 Close suffixes, far suffixes, and the $k$-words tree

Let $k$ be an integer parameter. We start by defining a simple yet useful data
structure.

######  Definition 17.

For a string $S[1\ldots n]$, the $k$-words tree of $S$ is a balanced search
tree with the following components:

  1. 1.

For every distinct $k$-length subword $w$ of $S$, the $k$-words tree contains
a node $v=N(w)$ corresponding to $w$.

  2. 2.

The nodes of the $k$-words tree are sorted by lexicographical order of their
corresponding words.

  3. 3.

$N(w)$ stores a balanced search tree containing the starting indexes of every
occurrence of $w$ in $S$ in increasing order. $N(w)$ also stores the number of
words in the subtree rooted in $N(w)$.

Let $v$ be a node in the $k$-words tree. We call the word $w$ such that
$N(w)=v$ the word of $v$. We denote the word of $v$ as $W(v)$. We point out
the distinction between nodes and words: every node in the $k$-words tree
represents a set of occurrences of certain sub-words. The number of words in a
subtree of the $k$-words tree is the accumulated number of occurrences
represented by the nodes of the sub-tree. The following theorem is proven in
[4].

######  Theorem 18 ([4], Lemma 3).

Given a string $S[1\ldots n]$, a data structure for dynamically maintaining
the $k$-words tree of $S$ can be constructed in $\tilde{\mathcal{O}}(n)$ time
using $O(n)$ space. When applying an edit operation update to $S$, the
$k$-words tree can be updated in $\tilde{\mathcal{O}}(k)$ time.

In [4], Lemma 3 is proved with respect to substitution updates. It can be
easily modified to support deletion and insertions as well.

We proceed to define far and close suffixes.

######  Definition 19.

Let $S^{i}=S[i\ldots n]$ and $S^{j}=S[j\ldots n]$ be two suffixes of a text
$S[1\ldots n]$. $S[i\ldots n]$ and $S[j\ldots n]$ are called close suffixes
(or $k$-close suffixes) if $LCP(i,j)\geq k$, and far suffixes (or $k$-far
suffixes) otherwise.

When we discuss $k$-close and $k$-far suffixes throughout the paper, the value
of $k$ is clear from context. We therefore use the notations ‘close’ and ‘far’
suffixes, omitting the specific value of $k$.

The primary role of the $k$-words tree is to apply a reduction from a query
about the suffix array to a query about close suffixes. Note that the starting
indexes of close suffixes are stored within the same node of the $k$-words
tree while the starting indexes of far suffixes are stored within different
nodes.

###  3.2 Dynamic Inverted Suffix Array

Reporting $iSA_{S}[i]$ is equivalent to counting the number of suffixes that
are lexicographically smaller than $S[i\ldots n]$. Upon a query integer $i$
for $iSA[i]$, we can find the node $v$ in the $k$-words tree with
$W(v)=S[i\ldots i+k-1]$ in $O(\log^{2}(n))$ time by applying a classic binary
tree search. The lexicographical comparison required in every node can be
executed in $O(\log(n))$ time by employing Lemma 11.

By counting the words to the left of the path from the root to $v$, we obtain
the amount of suffixes of $S$ that are lexicographically smaller than
$S[i\ldots n]$ and are far from $S[i\ldots n]$. Given the path, this can be
easily executed in logarithmic time. The remaining problem is to find the
number of suffixes close to $S[i\ldots n]$ that are lexicographically smaller
than $S[i\ldots n]$.

We formalize the problem of finding the close smaller suffixes as follows:

Close Suffixes Rank
Given an index $i$ representing a suffix $S[i\ldots n]$, return lexicographic
rank of $S[i\ldots n]$ among the suffixes close to $S[i\ldots n]$.

In this paper, we present a dynamic data structures for Close Suffix Rank
queries. Specifically, we prove the following in Section 5.

######  Theorem 20.

Given a dynamic text $S[1\ldots n]$, there is a data structure that supports
Close Suffixes Rank queries in $O(\log^{4}(n))$ time for $k=\sqrt{n}$. The
data structure can be maintained in $\tilde{\mathcal{O}}(\sqrt{n})$ when a
substitution update is applied to $S$.

With Theorem 20, and the above reduction using the $k$-words tree, our main
result for inverted suffix array is trivially achieved:

######  Theorem 21.

Given a dynamic string $S[1\ldots n]$ there is a data structure that reports
$iSA_{S}[i]$ in $O(\log^{4}(n))$ time. The data structure can be maintained in
$\tilde{\mathcal{O}}(\sqrt{n})$ time when a substitution update is applied to
$S$. The data structure uses $\tilde{\mathcal{O}}(n)$ space.

###  3.3 Dynamic Suffix Array

A query $i$ for $SA_{S}[i]$ can also be reduced to a query about close
suffixes using the $k$-words tree by applying the following recursive
algorithm:

$Findvr(Root,i)$:
Input: An integer $i$ and a node $Root$ in the $k$-words tree. Initially the
root. Output: A node $v$ and an integer $r$. Let $R$ and $L$ be the right and
the left children of $Root$, respectively. Let $|T(R)|$, $|T(L)|$ be the
number of words in the trees rooted in $R$ and in $L$, respectively. Let
$|Root|$ be the number of words contained in the root node. 1. If $|T(L)|\geq
i$ return $Findvr(L,i)$. 2. If $|T(L)|+|Root|\geq i$ return the tuple
$(Root,i-|T(L)|)$. 3. If $|T(L)|+|Root|<i$ return $Findvr(R,i-|T(L)|-|Root|)$

The following can be easily verified:

######  Fact 22.

Applying Algorithm $Findvr(R,i)$ with $R$ the root of the $k$-words tree of
$S$ yields the node $v$ containing $SA[i]$ and the lexicographic rank $r$ of
$SA_{S}[i]$ within the suffixes close to $SA_{S}[i]$. The time complexity of
Algorithm $Findvr$ is $O(\log(n))$.

With that, reporting $SA[i]$ is reduced to a Close Suffix Selection Query
defined below.

Close Suffixes Select
Given a subword of size $k$ represented as an index $i\in[1\ldots n-k+1]$ and
a rank $r$, return the suffix $S[i\ldots n]$ with lexicographic rank $r$ among
the suffixes starting with $S[i\ldots i+k-1]$

In Section 4, we prove the following:

######  Theorem 23.

Given a dynamic text $S[1\ldots n]$, there is a data structure that support
close suffixes selection queries in $O(\log^{5}(n))$ time. The data structure
can be maintained in $\tilde{\mathcal{O}}((\frac{n}{k})^{2}+k)$ time when an
edit operation is applied to $S$. The data structure uses
$\tilde{\mathcal{O}}(n+(\frac{n}{k})^{2})$ space.

By setting $k=n^{\frac{2}{3}}$ and applying the above reduction with a
$k$-words tree, we obtain the following:

######  Theorem 24.

For a dynamic string $S[1\ldots n]$, there is a data structure that supports
look up queries to $SA_{S}[i]$ in $O(\log^{5}(n))$ time. When an edit
operation update is applied to $S$, the data structure can be maintained in
$\tilde{\mathcal{O}}(n^{\frac{2}{3}})$ time. The data structure uses
$\tilde{\mathcal{O}}(n)$ space.

##  4 Dynamic Close Suffix Select Queries

In this section, we present the main idea for proving Theorem 23. Let $w$ be a
word of size $t=\frac{k}{2}$. We denote as $POR_{w}$ the periodic occurrences
representation of $w$ in $S[1\ldots n]$ and $Occ_{w}$ the set of occurrences
of $w$. We denote as $A_{w}[1\ldots|Occ_{w}|]$ the array consisting of the
starting indexes of occurrences of $w$ sorted by lexicographic order of the
suffixes starting in these indexes. The size of $POR_{w}$ is bounded by
$O(\frac{n}{k})$ while the size of $A_{w}$ may be $\Omega(n)$.

Let $C=(a,b,p)\in POR_{w}$ be a periodic cluster of occurrences of $w$ with
period $per(w)=p$.

######  Definition 25.

Let $w_{t}=S[s_{t}\ldots e_{t}]$ be an occurrence implied by $C$ of
$w=S[s\ldots e]$ and let $w_{s}=w[e-p+1\ldots e]$ be the suffix of size $p$ of
$w$. The period rank of $w_{t}$, denoted as $r_{p}(w_{t})$, is the maximal
integer $x$ such that $S[e_{t}+1\ldots e_{t}+p\cdot x]=(w_{s})^{x}$.
Equivalently, $r_{p}(w_{t})$ is the maximal number of consecutive occurrences
of $w_{s}$ following $w_{t}$.

One can easily observe that the $t$’th occurrence in $C$ has
$r_{p}(w_{t})=|C|-t-1$. (Recall that the occurrences within a cluster are
indexed with zero based indexes)

######  Definition 26 (Cluster Head, Cluster Tail, Increasing and Decreasing
Clusters).

Let $w_{0}=S[s_{0}\ldots e_{0}]$ and $w_{|C|-1}=[s_{|C|-1}\ldots e_{|C|-1}]$
be the leftmost and the rightmost occurrence of $w$ represented by $C$,
respectively (with respect to starting index). Let $w_{s}=w[e-p+1\ldots e]$ be
the suffix of size $p$ of $w$. We call the prefix $S[1\ldots s_{0}-1]$ the
head of $C$ denoted as $Head(C)$ and the suffix $S[e_{|C|-1}+1\ldots n]$ the
tail of $C$ denoted as $Tail(C)$. We call $C$ an increasing cluster if
$Tail(C)>_{L}w_{s}$, or a decreasing cluster if $Tail(C)<_{L}w_{s}$.

Figure 1: Periodic cluster of occurrences and its properties. The lines above
the string segment denote the occurrences implied by the cluster. Note that in
this example, $Tail(C)=bab\ldots>baa=w_{s}$. Therefore, the cluster is
increasing.

See Figure 1 for an example of a cluster and its properties. In Section 7, we
prove that $A_{w}$ has the following structure (derived from Lemma 74 and
Lemma 75):

$A_{w}$ can be described as a concatenation
$A_{w}=D[1\ldots|D|],I[1\ldots|I|]$ with $D$ being the sub array containing
the set of occurrences implied by decreasing clusters, and $I$ being the set
of occurrences implied by increasing clusters.

$D$ can be written as the concatenation $D=D_{0},D_{1}\ldots D_{m-1},D_{m}$.
$m$ is the maximal period rank of an occurrence in a decreasing cluster. For
every $r\in[0\ldots m]$ , $D_{r}$ contains the occurrences $w^{\prime}$ from
decreasing clusters with $r_{p}(w^{\prime})=r$ sorted by lexicographic order
of the tails of their clusters.

Similarly, $I=I_{t},I_{t-1}\ldots I_{1},I_{0}$. $t$ is the maximal period rank
of an occurrence in an increasing cluster. For every $r\in[0\ldots t]$ ,
$I_{r}$ contains the occurrences $s$ from increasing clusters with
$r_{p}(s)=r$ sorted by lexicographic order of the tails of their clusters (See
Figure 8).

Let $w=S[s\ldots e]$ be a subword of $S$. Let $l$ and $r$ be two non-negative
integers.

######  Definition 27.

An occurrence $w_{1}=S[s_{1}\ldots e_{1}]$ of $w$ is an $(l,r)$-extendable
occurrence of $w$ if $lcs(s-1,s_{1}-1)\geq l$ and $lcp(e+1,e_{1}+1)\geq r$. We
define the array $A^{(l,r)}_{w}$ as the lexicographically sorted array of
suffixes of $S$ starting with an $(l,r)$-extendable occurrence of $w$.

It is easy to see that given a word $w^{c}=S[s-l\ldots e+r]$ containing $w$,
an occurrence of $w^{c}$ in index $i$ is equivalent to an $(l,r)$-extendable
occurrence of $w$ in $i+l$. Therefore, $A_{w^{c}}[i]=A^{(l,r)}_{w}[i]-l$ for
every $i\in[1\ldots|A_{w^{c}}|]$. We consider the following problem:

Extension Restricting Selection
Preprocess: A word $w=S[s\ldots e]$ and $POR_{w}$ Query: upon input $l,r,i$.
Report $A^{(l,r)}_{w}[i]$

In Section 7, we prove the following:

######  Theorem 28.

If $LCE$ queries can be evaluated in $O(\log(n))$ time, 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 Selection queries in $O(\log^{5}(n))$ time. The data structure
uses $\tilde{\mathcal{O}}(|POR_{w}|)$ space.

Constructing the data structure described in Theorem 28 is the most
technically involved part in the construction of our dynamic suffix array data
structure. It is achieved by exploiting the characterization of the structure
of $A_{w}$. Our insights on the structure of $A_{w}$ allow us to reduce an
Extension Restricting Selection query to a small set of multidimensional range
queries.

We are now ready to present the algorithm for dynamic Close Suffix selection
queries. We initialize a data structure for supporting dynamic $LCE$ queries
on $S$ by employing Lemma 11. We also initialize a dynamic data structure for
obtaining periodic occurrences representations by employing Fact 15. Let
$t=\lfloor\frac{k}{2}\rfloor$. We partition $S$ into words of size $t$
starting in indexes $i=0\bmod t$. For every word $w_{x}=S[x\cdot
t\ldots(x+1)\cdot t-1]$ for $x\in[0\ldots\lfloor\frac{n}{t}\rfloor]$, we
obtain $POR_{w_{x}}$ in $\tilde{\mathcal{O}}(\frac{n}{t})$ time. We preprocess
$POR_{w_{x}}$ for Extension Restricting Selection queries using Theorem 28. We
keep an array $ERSQ[1\ldots\lfloor\frac{n}{t}\rfloor]$ with $ERSQ[x]$
containing a pointer to the Extension Restricting Selection queries data
structure of $w_{x}$.

Upon an edit operation update, we update the data structures for $LCE$ queries
and for obtaining the periodic occurrence representation. We then partition
the updated $S$ in the same manner as in the initialization step. Note that
the words in the partition may change, as the size of $S$ may change due to an
insertion or a deletion update, and $k$ may be a function of $|S|=n$. For
every word $w_{x}$ in the updated partition, we extract $POR_{w_{x}}$ and
evaluate the extension restricting selection queries data structures for every
word $w_{x}$ from scratch. We also construct the array $ERSQ$ from scratch as
in the initialization step.

Upon a Close Suffix Selection query $(i,r)$, the word
$w_{\lceil\frac{i}{t}\rceil}$ is completely contained within $w=S[i\ldots
i+k-1]$. Let $L$ be the distance between the starting indexes of
$w_{\lceil\frac{i}{t}\rceil}$ and $w$ and let $R$ be the distance between the
ending indexes. We execute an Extension Restricting Selection query $(L,R,r)$
on the Extension Restricting Selection queries data structure of
$w_{\lceil\frac{i}{t}\rceil}$. Let the output of the query be $z$. We return
$z-L$ .

Correctness: A Close Suffix Selection query $(i,r)$ is equivalent to reporting
$A_{w}[r]$. Denote the indexes of $w_{\lceil\frac{i}{t}\rceil}=S[s\ldots e]$.
The word $w=S[i\ldots i+k-1]$ can be written as $w=S[s-L,e+R]$. Therefore,
$A_{w}[r]=A^{(L,R)}_{w_{\lceil\frac{i}{t}\rceil}}[r]-L$.

Preprocessing time: The preprocessing times of the $LCE$ data structure and
the periodic occurrences data structure are both bounded by
$\tilde{\mathcal{O}}(n)$. The remaining operations are, in fact, an initial
update. The complexity analysis for these is provided below.

Update time: Evaluating the partition can be executed in $O(\frac{n}{k})$ time
in a straightforward manner. There are $\frac{n}{t}\in O(\frac{n}{k})$ words
in our partition. For every word $w$, we find $POR_{w}$ in
$\tilde{\mathcal{O}}(\frac{n}{k})$ time. Since $|w|=\frac{k}{2}$, we have
$|POR_{w}|\in O(\frac{n}{k})$. So constructing the Extension Restricting
Selection data structure from $POR_{w}$ takes
$\tilde{\mathcal{O}}(\frac{n}{k})$. The update time for the $LCE$ data
structure is polylogarithmic and the update time for the periodic occurrences
representation data structure is $\tilde{\mathcal{O}}(k)$. The overall update
complexity is dominated by $\tilde{\mathcal{O}}((\frac{n}{k})^{2}+k)$.

Space: The space consumed by the Extension Restricting Selection data
structures is bounded by $\tilde{\mathcal{O}}((\frac{n}{k})^{2})$. The space
consumed by the array $ERSQ$ is bounded by $O(\frac{n}{k})$. The space
consumed by the data structure for periodic occurrences representation is
bounded by $O(n)$. The space consumed by the $LCE$ data structure is bounded
by $\tilde{\mathcal{O}}(n)$. The overall space complexity is bounded by
$\tilde{\mathcal{O}}(n+(\frac{n}{k})^{2})$.

Query time: The query consists of a constant number of basic arithmetic
operations, a single array lookup and a single Extension Restricting Selection
query. The query time is dominated by $O(\log^{5}(n))$. ∎

##  5 Dynamic Close Suffixes Rank Queries

In this section, we set $k=\sqrt{n}$ to be the threshold parameter for
distinguishing between close and far suffixes.

We denote the rank of a suffix $S[i\ldots n]$ among the suffixes close to
$S[i\ldots n]$ as $r(i)$. The following lemma is required to initialize our
data structure.

######  Lemma 29.

$r(i)$ can be evaluated for all the suffixes of $S[1\ldots n]$ in $O(n)$ time

Proof: Construct the suffix array $SA[1\ldots n]$ and $LCP$-Array $LA[1\ldots
n]$, where $LA(i)=LCP(SA[i-1],SA[i])$, in $O(n)$ time [39, 21]. We set
$r(1)=0$ and proceed to set $r(i)$ for $i\in[2\ldots n]$ in increasing order
of $i$.

If $LA[i]<k$ then $SA[i]$ is the lexicographically minimum among the suffixes
close to $SA[i]$. Therefore, we set $r(SA[i])=0$. If $LA[i]\geq k$ then
$SA[i]$ is close to $SA[i-1]$ and is the lexicographical successor of
$SA[i-1]$. Therefore, $SA[i]$ is larger than exactly $r(SA[i])=r(SA[i-1])+1$
close suffixes. Every index is treated in constant time and the overall time
is linear. ∎

Our dynamic data structure for close suffixes rank queries is an ‘array’ of
integers $R[1\ldots n]$, initialized as the initial close suffix ranks
calculated by Lemma 29 ($R[i]=r(i)$). When a substitution update is applied to
$S$ the ranks $r(i)$ of the suffixes change. We wish to change $R[i]$ in a
corresponding manner.

We provide an analysis of the updates that are need to be applied to $R$ when
a symbol substitution is applied to $S$. Unsurprisingly, these changes are too
wild to be efficiently applied to an ordinary array (e.g. - $\Omega(\sqrt{n})$
indexes may have to be updated). However, the updates to the ranks can be
described as a small set of interval increment and stairs updates on $R$.

######  Definition 30.

An interval increment update is denoted by $I=(i,j,x)$. Applying $I$ to $R$
increases the value of $R[a]$ by $x$ for $a\in[i\ldots j]$.

######  Definition 31.

A decreasing stairs update (See Figure 2) is denoted by $S=(i,j,p)$. Applying
$S$ to $R$ increases the value of the indexes in $R[i\ldots j]$ as follows:
the rightmost $p$ indexes $R[j-p+1\ldots j]$ are increased by $1$, the $p$
indexes to their left are increased by $2$, and so on until we finally exceed
$R[i\ldots j]$.

Formally, for every $t\in[1\ldots\lceil\frac{j-i+1}{p}\rceil]$, the counters
$R[a]$ with $a\in[max(j-t\cdot p+1,i)\ldots j-(t-1)\cdot p]$ are increased by
$t$.

We call $p$ the step width of the stairs update $S$. We call the interval
increased by exactly $t$ the $t$’th step of the update.

Figure 2: A visualization of an application of a decreasing stairs update and
its properties. The update $S$ is applied to the array $R$ to obtain
$R^{\prime}$.

An increasing stairs update is defined symmetrically, with the ‘stairs’ having
increasing (rather than decreasing) values from left to right. A stairs update
can also be a negative update, decreasing the values of the $t$’th step by $t$
rather than increasing it by $t$. A formal definition of these variants can be
found in Section 8.

######  Example 32.

Let $R=(0,0,0,0,0,0,0,0,0,0)$. Applying a decreasing stairs update $(3,8,2)$
on $R$ will result in $R=(0,0,4,3,3,2,2,1,1,0,0)$. Applying an increasing
stairs update $(2,8,3)$ instead will result in
$R^{\prime}=(0,1,1,1,2,2,2,3,3,0,0)$. Applying a negative decreasing stairs
update $(4,10,2)$ on $R^{\prime}$ will result in
$R^{\prime}=(0,1,1,-3,-2,-1,-1,1,1,-1,-1)$.

In section 8, we prove the following:

See 2

For the sake of self containment, we provide a proof for the following
(simple, possibly folklore) claim:

######  Claim 33.

There is a data structure for maintaining an indexed set of integers $R$ to
support both applying an interval increment update to $R$ and look-up queries
$R[i]$ in time $O(\log(n))$.

Our algorithm may require stairs updates with varying values of $p$. We will
eventually describe the details for how the restricted data structure of
Theorem 2 is utilized. Until then, we refer to stairs update application and
query as an $O(\log^{3}(n))$ time procedure. We want stairs updates to be
executed in $O(\log^{3}(n))$ rather than $O(\log^{3}(U))$. This can be
achieved in amortized time by rebuilding our data structure from scratch after
every $O(n)$ updates. The running time can be deamortized using standard
techniques.

From now on, we fix $x\in[1\ldots n]$ to be the index within $S[1\ldots n]$
such that $S[x]$ was substituted. By $S$ we refer to the text after the update
was applied, and by $T$ we refer to the text prior to the substitution. For an
index $i\in[1\ldots n]$, we denote the word $w^{new}_{i}=S[i\ldots i+k-1]$ and
$w^{old}_{i}=T[i\ldots i+k-1]$. For $w^{new}_{i}$ and $w^{old}_{i}$ to be
defined for every $i\in[1\ldots n]$, we process $S$ as if it has the string
$\$^{k}$ appended to its end for some symbol $\$\notin\Sigma$ that is
lexicographically smaller than every symbol $\sigma\in\Sigma$. Note that this
does not affect the lexicographical order between the suffixes of $S$.

Consider the following clustering of the suffixes of $S$: two suffixes $T^{i}$
and $T^{j}$ are in the same cluster if and only if they are closed.
Equivalently, every cluster $C$ corresponds to a word $w_{C}$ and a suffix
$T^{i}$ is in $C$ if and only if $w^{old}_{i}=w_{C}$. Even though we do not
explicitly maintain such a clustering in our data structure, it is helpful to
think of the suffixes of $S$ as if they are stored in this manner.

Observe that $R[i]$ is the lexicographic rank of $T^{i}$ among the suffixes in
$C_{w^{old}_{i}}$. After an update is applied to $T$, $R[i]$ needs to be
modified to be the rank of $S^{i}$ among the suffixes in a possibly different
cluster $C_{w^{new}_{i}}$. We distinguish between two types of suffixes:

  1. 1.

Dynamic suffixes:  $S^{i}$ with $x\in[i\ldots i+k-1]$: For these suffixes,
$w^{old}_{i}\neq w^{new}_{i}$.

  2. 2.

Static suffixes: $S^{i}$ with $x\notin[i\ldots i+k-1]$. For these suffixes,
$w^{old}_{i}=w^{new}_{i}$

Note that dynamic suffixes are suffixes that are moved to a different cluster
as a result of the update, and static suffixes are the suffixes that stay in
the same cluster after the update is applied. We partition the updates applied
to $R$ into $3$ types:

  1. 1.

Evaluation Updates \- Evaluating $R[i]$ for every dynamic suffix $S^{i}$.

  2. 2.

Shift Updates \- Increasing (resp. decreasing) by $1$ the values of $R[i]$ for
a static suffixes $S^{i}$ as a result of a dynamic suffix $S^{j}$ that has
$w^{new}_{j}=w^{new}_{i}$ (resp. $w^{old}_{j}=w^{old}_{i}$) and
$S^{j}<_{L}S^{i}$ (resp. $T^{j}<T^{i}$) (See Figure 3).

  3. 3.

Overtakes \- For a pair of close static suffixes $S^{i}$,$S^{j}$ such that
$S^{i}>_{L}S^{j}$ and $T^{i}<_{L}T^{j}$, increasing the value of $R[i]$ by 1
and decreasing the value of $R[j]$ by 1 (See Figure 4).

An evaluation update corresponds to evaluating the rank of a dynamic suffix
within the new cluster for which it was recently inserted. A shift update
corresponds to an increase (resp. decrease) in the rank of a static suffix
$S^{i}$ as a result of a dynamic suffix that is lexicographically smaller than
$S^{i}$ being inserted (resp. deleted) from the cluster of $S_{i}$. An
overtake corresponds to a change in lexicographical order between two static
suffixes within the same cluster.

Figure 3: A visualization of a shift update. The (mostly) red rectangles
resemble $w^{old}_{i}$ and $w^{old}_{j}$. In $T$, the words $w^{old}_{i}$ and
$w^{old}_{j}$ are identical, except for the marked non-red rectangle, which
represents a ‘blue’ symbol in $w^{old}_{i}$ and a ‘green’ symbol in the
corresponding location in $w^{old}_{j}$. The blue arrows to the right of
$w^{old}_{i}$ and $w^{old}_{j}$ resemble the $LCP$ between $i+k-1$ and
$j+k-1$. In this example, the green symbol in $w^{old}_{j}$ is modified by an
update to a blue symbol, so we have $w^{new}_{i}=w^{new}_{j}$. The symbol
following the $LCP$ after $i$ is $1$, and the symbol following the $LCP$ after
$j$ is $0$, so we have $S^{j}<_{L}S^{i}$. The suffix $S^{j}$ became close to
$S^{i}$ as a result of the last substitution, so $r(i)$ is increased by $1$.
The reason is that we have a new suffix close to $S^{i}$ that is
lexicographically smaller than $S^{i}$.  Figure 4: A visualization of an
overtake update. The red rectangles resemble $w^{old}_{i}$ and $w^{old}_{j}$,
and we have $w^{old}_{i}=w^{old}_{j}$, so $T^{i}$ and $T^{j}$ are close
suffixes. The substitution occurs in an index that is not contained either in
$w^{old}_{i}$ or in $w^{old}_{j}$, therefore they are both static suffixes.
The $lcp$ between $i+k-1$ and $j+k-1$ is denoted by the blue arrows. Prior to
the update, the $lcp$ terminates in a $1$ following $S^{i}$ and in a $0$
following $j$. Therefore, $T^{i}>_{L}T_{j}$. After the update is applied, the
$lcp$ is extended by $1$ symbol and we have $S^{i}<_{L}S_{j}$, so $S^{j}$
overtakes $S^{i}$. The rank of $S^{i}$ should be decreased by $1$ and the rank
of $S^{j}$ should be increased by $1$

It should be clear that if we apply all the evaluation updates, all the shift
updates, and all the overtake updates to $R$, then $R$ is properly set and
$R[i]=r(i)$ for every $i\in[1\ldots n]$ with respect to the close suffix ranks
$r(i)$ in the updated text $S$. In the following sections we show how to
efficiently apply these types of updates to $R$.

###  5.1 Evaluation updates

In this section, we present an $O(\sqrt{n})$ time algorithm for evaluating
$r(i)$ for $i\in[x-k+1\ldots x-\frac{k}{2}+1]$. These are only half of the
dynamic suffixes. We conclude by explaining how the same techniques can be
used to construct a similar algorithm to evaluate $r(i)$ for
$i\in[x-\frac{k}{2}\ldots x]$.

The task of evaluating $r(i)$ can be equivalently described as a counting
problem. Specifically, $r(i)$ is the number of suffixes $S^{j}$ starting with
$w^{new}_{i}$ such that $S^{j}<_{L}S^{i}$. With that characterization in mind,
a naive approach would be the following: Iterate the values $i\in[x-k+1\ldots
x]$ and for every value, evaluate the set of close suffixes and count how many
of these are lexicographically smaller than $S^{i}$. An explicit
straightforward execution of this idea would result in an algorithm with
running time $\tilde{\mathcal{O}}(n^{1.5})$, since the number of dynamic
suffixes is $O(k)=O(\sqrt{n})$ and the number of suffixes close to a certain
dynamic suffix can not be bounded by anything smaller than $O(n)$. Of course,
this is not a satisfactory running time. We present an implementation of the
naive algorithm that exploits the structure of the problem to achieve a time
complexity of $\tilde{\mathcal{O}}(\sqrt{n})$.

Our enhanced implementation of the naive approach relies on exploiting the
proximity of the starting indexes of the words $w_{i}^{new}$ corresponding to
dynamic suffixes $S^{i}$. Instead of evaluating the set of occurrences of
$w_{i}^{new}$ for every $i\in[x-k+1\ldots x-\frac{k}{2}+1]$, we consider the
occurrences of the word $w^{c}_{l}=S[x-\frac{k}{2}+1\ldots x]$. Note that
$w^{c}_{l}$ is a subword of all the words $w_{i}^{new}$ with $i\in[x-k+1\ldots
x-\frac{k}{2}+1]$. We use an occurrence of $w^{c}_{l}$ as an anchor that may
be extendable to an occurrence of $w_{i}^{new}$ for some values of $i$. Since
$w^{c}_{l}$ has length $\Theta(k)$, the occurrences of $w^{c}_{l}$ in $S$ can
be represented as a set of $O(\frac{n}{k})=O(\sqrt{n})$ clusters (Fact 14). We
provide a method to efficiently process a cluster $C$ of occurrences of
$w^{c}_{l}$ to deduce the modifications to $r(i)$ that are required as a
result of occurrences represented by $C$.

To simplify notations, we define the function
$D(\delta)=x-\frac{k}{2}+1-\delta$. Upon input integer $\delta$, the function
$D(\delta)$ outputs the index in $S$ that is $\delta$ indexes to the left from
the starting index of $w^{c}_{l}$. The following fact captures the relation
between the occurrences of $w^{c}_{l}$ and the suffixes that should be counted
by our algorithm.

(The indexes of $w^{c}_{l}$ are renamed to $S[s\ldots e]$ for clearer
presentation)

######  Fact 34.

Let $S^{i}$ be a dynamic suffix with $i=D(\delta)$ for some
$\delta\in[0\ldots\frac{k}{2}]$. For an index $j\in[1\ldots n]$, the following
are equivalent:

  1. 1.

$S^{j}$ is close to $S^{i}$ (starts with an occurrence of $w^{new}_{i}$) and
$S^{j}<_{L}S^{i}$.

  2. 2.

There is an occurrence $w_{1}=S[s_{1}\ldots e_{1}]$ of $w^{c}_{l}=S[s\ldots
e]$ in index $s_{1}=j+\delta$ such that $S^{s_{1}}<_{L}S^{s}$,
$lcs(s_{1}-1,s-1)\geq\delta$ and $lcp(e_{1}+1,e+1)\geq\frac{k}{2}-\delta$.

Figure 5: A visualization of Fact 34 with $k=12$. The upper segment is a
substring of $S$ surrounding the changed index $x$. The word $w^{c}_{l}$ is
“$bcabca$” ending in index $x$. The lower segment is a separated substring of
$S$ containing an occurrence of $w^{c}_{l}$ (aligned with the occurrence in
the upper segment). Every index within the blue interval marked in the lower
string is the starting index of an occurrence of its corresponding aligned
$w^{new}_{i}$

Fact 34 holds due to the fact that $w^{c}_{l}$ is a substring of $w^{new}_{i}$
for these values of $i$. An occurrence of $w^{new}_{i}$ is equivalent to an
occurrence of $w^{c}_{l}$ that has a sufficiently long common extension with
$w^{c}_{l}$. See Figure 5 for a visualization.

For $i=D(\delta)$ with $\delta\in[0\ldots\frac{k}{2}]$, we say that an
occurrence of $w^{new}_{i}$ in index $j$ is induced by the occurrence of
$w^{c}_{l}$ in index $j+\delta$.

We use Fact 34 to evaluate $r(i)$ for every $i\in[x-k+1\ldots
x-\frac{k}{2}+1]$ in a parallel manner. Instead of processing occurrences of
$w^{new}_{i}$ for every dynamic suffix $S^{i}$ with $i\in[D(\frac{k}{2})\ldots
D(0)]$, we process the occurrences of $w^{c}_{l}=S[s\ldots e]$. For every
occurrence of $w_{1}=S[s_{1}\ldots e_{1}]$, we identify values of $i$ for
which $w^{new}_{i}$ is induced by $w_{1}$ according to Fact 34. If
$S^{s_{1}}<_{L}S^{s}$, we count the induced suffixes as smaller close suffixes
of their corresponding dynamic suffixes.

A technical implementation of the above approach is given as Algorithm 1

###### Algorithm 1

Initialize an array of counters $Re[0\ldots\frac{k}{2}]$ with zeroes. . For
every occurrence $w=S[s_{1}\ldots e_{1}]$ of $w^{c}_{l}$: 1. Check if
$S^{s_{1}}<_{L}S^{s}$. If it is not - stop processing this occurrence. 2.
Compute $l=lcs(s_{1}-1,s-1)$ and $r=lcp(e_{1}+1,e+1)$. 3. Increase the
counters of $Re$ with indexes in $[max(0,\frac{k}{2}-r),\min(l,\frac{k}{2})]$
by $1$. For every $\delta\in[0\ldots\frac{k}{2}]$, set
$R[D(\delta)]\longleftarrow Re[\delta]$.

######  Claim 35.

By the end of the inner loop of Algorithm 1, $Re[\delta]=r(D(\delta))$

Proof: The counter $Re[\delta]$ is increased by $1$ as many times as an
occurrence $w=S[s_{1}\ldots e_{1}]$ of $w^{c}_{l}$ that satisfies the
following conditions is processed:

  1. 1.

$lcs(s_{1}-1,s-1)=l\geq\delta$

  2. 2.

$lcp(e_{1}+1,e+1)=r\geq\frac{k}{2}-\delta$

  3. 3.

$S^{s_{1}}<_{L}S^{s}$

According to Fact 34, there are exactly as many occurrences of $w^{c}_{l}$
satisfying these conditions as suffixes close to $S^{D(\delta)}$ that are
lexicographically smaller than $S^{D(\delta)}$. ∎

Assuming that we have the occurrences of $w^{c}_{l}$ in hand, Algorithm 1 can
be straightforwardly implemented in $\tilde{\mathcal{O}}(|occ(w^{c}_{l})|)$
time, with $occ(w^{c}_{l})$ being the set of occurrences of $w^{c}_{l}$ in
$S$. Since we may have $|w^{c}_{l}|\in\Theta(n)$, this is not sufficiently
efficient. To further reduce the time complexity, we process the periodic
occurrences representation of $w^{c}_{l}$ rather than the explicit set of
occurrences.

We use Lemma 15 with $x=\frac{k}{2}=|w^{c}_{l}|$ to obtain the periodic
occurrences representation of $w^{c}_{l}$ in
$\tilde{\mathcal{O}}(\frac{2n}{k})=\tilde{\mathcal{O}}(\sqrt{n})$ time. The
following is proven in section 6:

######  Lemma 36.

Let $C=(a,b,p)$ be a cluster of occurrences of a word $w=S[s\ldots e]$ with
$per(w)=p$ in $S[1\ldots n]$. Let the occurrences represented by $C$ be
$w_{0},w_{1}\ldots w_{|C|-1}$ with $w_{t}=S[s_{t}\ldots e_{t}]$ and
$s_{t}=a+t\cdot p$. Let $l_{t}=lcs(s_{t}-1,s-1)$ and $r_{t}=lcp(e_{t}+1,e+1)$.
Let $Ex_{l}$ and $Ex_{r}$ be the lengths of the extension of the run with
period $p$ containing $w$ to the left of $s-1$ and to the right of $e+1$,
respectively. Let $Ex^{C}_{l}$ and $Ex^{C}_{r}$ be the lengths of the
extension of the run with period $p$ containing $w_{0}$ to the left of
$s_{0}-1$ and to the right of $e_{0}+1$, respectively.

  1. 1.

If $Ex_{l}\neq Ex^{C}_{l}+p\cdot t$, we have
$l_{t}=\min(Ex_{l},Ex^{C}_{l}+p\cdot t)$.

  2. 2.

If $Ex_{r}\neq Ex^{C}_{r}-p\cdot t$, we have
$r_{t}=\min(Ex_{r},Ex^{C}_{r}-p\cdot t)$

The values of $Ex_{l}$, $Ex_{r}$, $Ex^{C}_{l}$ and $Ex^{C}_{r}$ can be
evaluated in $O(\log(n))$ time given $C$, the indexes of $w$, and a data
structure for $O(\log(n))$-time LCE queries.

For most of the occurrences $w_{t}$ represented by a cluster $C$, Lemma 36
provides a compact, efficiently computable representation of the common
extensions of $w_{t}$ and $w$. We note that every cluster may contain a
constant number of occurrences for which Lemma 36 does not provide a
representation of $l_{t}$ and $r_{t}$. We formally define these occurrences as
follows.

######  Definition 37.

Let $C=(a,b,p)$ be a cluster of occurrences of a word $w=S[s\ldots e]$ with
$per(w)=p$ in $S[1\ldots n]$. Let $Ex_{l}$, $Ex_{r}$, $Ex^{C}_{l}$ and
$Ex^{C}_{r}$ be the lengths of the extension of the runs as in Lemma 36.
$w_{t}$ is an aligned occurrence if $Ex_{l}=Ex^{C}_{l}+p\cdot t$ or
$Ex_{r}=Ex^{C}_{r}-p\cdot t$.

The aligned occurrences within a cluster $C$ can be easily found in constant
time given $C$, $w$ and the runs extension lengths. The two constrains
defining aligned occurrences are linear equations with respect to $t$.
Therefore, there is at most one value $t$ satisfying each equation and it can
be found in constant time.

For evaluation updates, we are only interested in the $LCE$ values that
correspond to occurrences $w_{t}$ with $S^{s_{t}}<_{L}S^{s}$. To extract these
values, we employ the following fact proven in Section 6.

######  Claim 38.

Let $s$ be an index and let $C=(a,b,p)$ be a periodic cluster with
$s_{t}=a+t\cdot p$. There are consecutive intervals
$I_{<},I_{>}\subseteq[0\ldots|C-1|]$ such that $S^{s_{t}}<_{L}S^{s}$ iff $t\in
I_{<}$ and $S^{s_{t}}>_{L}S^{s}$ iff $t\in I_{>}$. The intervals $I_{<}$ and
$I_{>}$ can be evaluated in $O(\log(n))$ time given $C$, $s$ and a data
structure for $O(\log(n))$ LCE queries.

Let $l_{t}=lcs(s-1,s_{t}-1)$ and $r_{t}=lcp(e+1,e_{t}+1)$. We evaluate a
compact representation of the list $L^{e}=l_{0},l_{1},l_{2}\ldots l_{|C|-1}$
by applying Lemma 36. We can obtain $I_{<}=[i\ldots j]$ by applying Claim 38.
Recall that we are interested in occurrences $w_{t}$ such that
$S^{s_{t}}<_{L}S^{s}$. So the relevant $lcs$ values are $l_{t}$ with $t\in
I_{<}$. We proceed to work on the reduced list $L_{<}=l_{i},l_{i+1}\ldots
l_{j}$. For similar arguments, we proceed to work on the reduced list
$R_{<}=r_{i},r_{i+1}\ldots r_{j}$ corresponding to the relevant values of
$r_{t}$.

So far, we characterized the structure of $lcp$ and $lcs$ values between a
word and a set of its occurrences represented by a cluster. In what follows,
we provide a method to efficiently apply the updates that are derived from
these values to $R$.

######  Definition 39 ($p$-Normal Sequence).

Let $B=b_{0},b_{1}\ldots b_{t}$ be a sequence of integers. $B$ is a $p$-normal
sequence for some integer $p$ if:

  1. 1.

$B$ is a fixed sequence: $b_{i}=b_{0}$ for every $i\in[1\ldots t]$, or

  2. 2.

$B$ is an arithmetic progression with difference $p$: $b_{i}=b_{0}+p\cdot t$
for every $i\in[1\ldots t]$, or

  3. 3.

$B$ is the maximum of two $p$-normal sequences:
$b_{i}=(max(a^{1}_{i},a^{2}_{i}))$ for two $p$-normal sequences
$\\{a^{1}_{i}\\}$ and $\\{a^{2}_{i}\\}$, or

  4. 4.

$B$ is the minimum of two $p$-normal sequences:
$b_{i}=(\min(a^{1}_{i},a^{2}_{i}))$ for two $p$-normal sequences
$\\{a^{1}_{i}\\}$ and $\\{a^{2}_{i}\\}$

The degree of a $p$-normal sequence is denoted as $deg(B)$. If $B$ is either
fixed or an arithmetic progression then $deg(B)=1$. If $B$ is a maximum
sequence with $b_{i}=(max(a^{1}_{i},a^{2}_{i}))$, or a minimum sequence with
$b_{i}=(\min(a^{1}_{i},a^{2}_{i}))$ then
$Deg(B)=Deg(\\{a^{1}_{i}\\})+Deg(\\{a^{2}_{i}\\})$.

Finally, the construction tree of a $p$-normal sequence $B$ is a full binary
tree denoted as $CT(B)$. It aims to represent the structure of $B$. If $B$ has
$deg(B)=1$ then $CT(B)$ consist of a single node. If $B$ is a maximum sequence
with $b_{i}=(max(a^{1}_{i},a^{2}_{i}))$, or a minimum sequence with
$b_{i}=(\min(a^{1}_{i},a^{2}_{i}))$ then $CS(B)$ consist of a root with the
left child being $CT(\\{a^{1}_{i}\\})$ and the right child being
$CT(\\{a^{2}_{i}\\})$

######  Example 40.

The sequence $A=4,7,10,13,16$ is a $3$-normal sequence with degree $1$, as it
is an arithmetic progression with difference $p=3$. $CT(A)$ is a single root
node $\\{A\\}$. The sequence $B=b_{0},b_{1}\ldots b_{t}$ with
$b_{i}=max(13,4+7\cdot t)$ is a $7$-normal sequence. The left input in the
$max$ expression is a fixed sequence with respect to $t$, which is a
$p$-normal sequence with degree $1$. The right sequence is an arithmetic
progression with difference $7$ with respect to $t$, which is a $7$-normal
sequence with degree $1$. therefore, $deg(B)=1+1=2$. $CS(B)$ is a root node
with two leaf children corresponding to the construction trees of
$[7,7,7\ldots]$ and of $[4,11,18\ldots]$.

The following lemma is proven in Section 6

######  Lemma 41.

Let $U=u_{1},u_{2}\ldots u_{|U|-1}$ be a set of interval increment updates
with $u_{t}=(i_{t},j_{t},1)$ and both $\\{i_{t}\\}$ and $\\{j_{t}\\}$ being
$p$-normal sequences for some integer $p$ with degrees
$Deg(\\{i_{t}\\}),Deg(\\{j_{t}\\})\in O(1)$. Applying all the interval updates
in $U$ is equivalent to applying a constant number of interval increment
updates and stairs updates with stair width $|p|$ to $R$. The set of
equivalent stairs and interval updates can be evaluated in constant time given
the representation of $i_{t}$ and $j_{t}$ as $p$-normal sequence (The input
can be given, for example, as the construction trees of $\\{i_{t}\\}$ and
$\\{j_{t}\\}$).

Consider the occurrence $w_{t}$ of $w^{c}_{l}$ starting in index $s_{t}$
represented by $C$ for some $t\in I_{<}=[i_{<}\ldots j_{<}]$. When $w_{t}$ is
iterated in Algorithm 1, the interval increment
$(max(0,r_{t}-\frac{k}{2}),\min(l_{t},\frac{k}{2}),1)$ is applied to $Re$.
Denote the left border of the interval increment applied when $w_{t}$ is
iterated as $i_{t}=max(0,r_{t}-\frac{k}{2})$ and the right border as
$j_{t}=\min(l_{t},\frac{k}{2})$. We make the following claim:

######  Claim 42.

Given $C$, $w=S[s\ldots e]$ and $I_{<}$, all the updates
$u_{t}=(i_{t},j_{t},1)$ for $t\in I_{<}$ can be applied to $Re$ in time
$O(\log^{3}(n))$.

Proof: Let $Al$ be the set of aligned occurrences within $C$. It is known that
$|Al|\leq 2$. Denote the set of aligned occurrences as $Al=\\{t_{1},t_{2}\\}$
with $t_{1}<t_{2}$. If $|Al|\leq 1$, we set $t_{2}=\rotatebox{90.0}{8}{}$. If
$|Al|=0$, we set $t_{1}=-\rotatebox{90.0}{8}{}$. For $t\notin Al$ we have
$Ex_{r}\neq Ex^{C}_{r}-p\cdot t$ and $Ex_{l}\neq Ex^{C}_{l}-p\cdot t$ .
Therefore, $i_{t}=max(0,\min(Ex_{r}-\frac{k}{2},Ex^{C}_{r}-\frac{k}{2}-p\cdot
t))$ and $j_{t}=\min(\min(Ex_{l},Ex^{C}_{l}-p\cdot t),\frac{k}{2})$ according
to Lemma 36. These are $(-p)$-normal sequence with degree $d_{i}=3$. For the
integers in $I_{1}=[i_{<}\ldots t_{1})$, both $\\{i_{t}\\}$ and $\\{j_{t}\\}$
are $p$-normal sequences. The same applies for the intervals
$I_{2}=(t_{1}\ldots t_{2})$ and $I_{3}=(t_{2}\ldots j_{<}]$. All the updates
$u_{t}$ for $t\in I_{1}\cup I_{2}\cup I_{3}$ can be expressed as a constant
number of stairs updates by applying Lemma 41 for every interval. Interval
updates corresponding to aligned occurrences can be applied in $O(\log(n))$
time each by employing Claim 33. Applying a constant number of stairs and
interval updates can be executed in $O(\log^{3}(n))$ time by Theorem 2. The
representations of $r_{t}$ and $l_{t}$ can be obtained in $O(\log(n))$ time by
employing Lemma 36. ∎

We are now ready to present an efficient implementation of Algorithm 1.

###### Algorithm 2

Initialize an array of counters $Re[0\ldots\frac{k}{2}]$ with zeroes.  Obtain
the periodic occurrences representation $por$ of $w^{c}_{l}$. For every
singular occurrence $w=S[s_{1}\ldots e_{1}]$ in $por$: 1. Check if
$S^{s_{1}}<_{L}S^{s}$. If it is not, then stop processing this occurrence. 2.
Compute $l=lcs(s_{1}-1,s-1)$ and $r=lcp(e_{1}+1,e+1)$. 3. Increase the
counters of $Re$ with indexes in $[max(0,r-\frac{k}{2}),\min(l,\frac{k}{2})]$
by $1$. For every cluster $C=(a,b,c)$ of occurrences in $por$: 1. Obtain
$I_{<}$ using Claim 38. 2. Apply all the updates corresponding to occurrences
$w_{t}$ with $t\in I_{<}$ implied by $C$ by employing Claim 42. For every
$\delta\in[0\ldots\frac{k}{2}]$, set $R[D(\delta)]\longleftarrow Re[\delta]$.

It is straightforward that the updates applied to $Re$ in Algorithm 2 are
equivalent to the updates applied to $Re$ in Algorithm 1. Therefore, the close
suffix ranks evaluated in $Re$ are correct directly from Claim 35.

######  Claim 43.

Algorithm 2 runs in $\tilde{\mathcal{O}}(\sqrt{n})$ time.

Proof: Since $|w^{c}_{l}|=\frac{k}{2}$, the size of the periodic occurrences
representation is $\frac{2n}{k}\in O(\sqrt{n})$ and it can be obtained in time
$\tilde{\mathcal{O}}(\sqrt{n})$ by applying Lemma 15.

For a singular occurrence in the representation, we process in logarithmic
time just as in Algorithm 1. For a cluster, we use Claim 38 and Claim 42 to
apply all the updates corresponding to occurrences implied by $C$. The
bottleneck of handling a cluster is the application of Claim 42 in
$O(\log^{3}(n))$ time. The overall time to process an element, either a
singular occurrence or a cluster, is polylogarithmic. Since there are
$O(\sqrt{n})$ elements in the representation. Algorithm 2 runs in
$\tilde{\mathcal{O}}(\sqrt{n})$ time. ∎

Note that Algorithm 2 initializes the data structure $Re$ for stairs updates
with a constant stair size $p$, uses it to evaluate the ranks and inserts its
values to the matching indexes in $R$. After the execution of Algorithm 2,
$Re$ can be discarded, since it is not used in future updates. The restricted
result of Theorem 2 is sufficient for this case.

This concludes the evaluation of the ranks for dynamic suffixes starting in
$[x-k+1\ldots x-\frac{k}{2}]$. We still need to handle the suffixes starting
in $[x-\frac{k}{2}+1\ldots x]$. This is done in the same manner, but instead
of $w^{c}_{l}=S[x-\frac{k}{2}+1\ldots x]$ we consider the occurrences of
$w^{c}_{r}=S[x\ldots x+\frac{k}{2}-1]$. One can easily verify that $w^{c}_{r}$
is a subword of every $w^{new}_{i}$ with $i\in[x-\frac{k}{2}+1\ldots x]$.

###  5.2 Shift updates

Shift updates are handled by applying the same observations that we used for
evaluation updates. We partition shift updates into two subtypes:

  1. 1.

Right shifts: A static suffix $S^{i}$ whose rank is increased by $1$ since
$w^{new}_{j}=w^{new}_{i}$ for some dynamic suffix $S^{j}<_{L}S^{i}$.

  2. 2.

Left shifts: A static suffix $S^{i}$ whose rank is decreased by $1$ since
$w^{old}_{j}=w^{old}_{i}$ for some dynamic suffix $S^{j}$ with
$T^{j}<_{L}T^{i}$.

We start by considering right shifts. For every static suffix $S^{i}$, we wish
to count the dynamic suffixes $S^{j}$ with $w^{new}_{j}=w^{new}_{i}$ and
$S^{j}<_{L}S^{i}$, and increase $R[i]$ by this number. Similarly to Section
5.1, we show how to increase the value of $R[i]$ for static suffixes $S^{i}$
by the amount of dynamic suffixes $S^{j}$ with $w^{new}_{i}=w^{new}_{j}$ such
that $S^{j}<S^{i}$ and $j\in[x-k+1\ldots x-\frac{k}{2}]$. The task of
increasing $R[i]$ by the amount of dynamic suffixes $S^{j}$ with
$w^{new}_{i}=w^{new}_{j}$ and $S^{j}<S^{i}$ for some
$j\in[x-\frac{k}{2}+1\ldots x]$ can be handled in a similar way by replacing
$w^{c}_{l}=S[x-\frac{k}{2}+1\ldots x]$ with $w^{r}_{l}=S[x\ldots
x+\frac{k}{2}-1]$.

We consider the following variation of Fact 34:

######  Fact 44.

Let $S^{i}$ be a dynamic suffix with $i=D(\delta)$ for some
$\delta\in[0\ldots\frac{k}{2}]$. For an index $j\in[1\ldots n]$, the following
are equivalent:

  1. 1.

$S^{j}$ is close to $S^{i}$ (starts with an occurrence of $w^{new}_{i}$) and
$S^{j}>_{L}S^{i}$.

  2. 2.

There is an occurrence $w_{1}=S[s_{1}\ldots e_{1}]$ of $w^{c}_{l}=S[s\ldots
e]$ in index $s_{1}=j+\delta$ such that $S^{s_{1}}>_{L}S^{s}$,
$lcs(s_{1}-1,s-1)\geq\delta$ and $lcp(e_{1}+1,e+1)\geq\frac{k}{2}-\delta$.

Similarly to Algorithm 1, we can construct an algorithm for increasing the
ranks of suffixes smaller than $S^{i}$ for every $i\in[1\ldots n]$ by
processing the occurrences of $w^{c}_{l}$ according to Fact 44.

###### Algorithm 3

For every occurrence $w=S[s_{1}\ldots e_{1}]$ of $w^{c}_{l}$: 1. Check if
$S^{s_{1}}>_{L}S^{s}$. If it is not - stop processing this occurrence. 2.
Compute $l=lcs(s_{1}-1,s-1)$ and $r=lcp(e_{1}+1,e+1)$. 3. Increase the
counters $R[i]$ with
$i\in[max(s_{1}-l,s_{1}-\frac{k}{2}),\min(e_{1}+r-k+1,s_{1})]$ by $1$.

Algorithm 3 is very similar to Algorithm 1. The main difference between these
two algorithms is that Algorithm 3 applies updates directly to $R$, unlike
Algorithm 1 that applies updates to a temporary array $Re$ and inserts the
final values to the matching indexes in $R$. This change is required because
shift updates may affect all the suffixes in $S$ while evaluation updates only
affects a small set of suffixes. We prove the following claim:

######  Claim 45.

For every $i\in[1\ldots n]$, the value of $R[i]$ is increased in the execution
of Algorithm 3 by the amount of dynamic suffixes $S^{j}$ with
$w^{new}_{i}=w^{new}_{j}$ and $j\in[x-k+1\ldots x-\frac{k}{2}]$ such that
$S^{j}<_{L}S^{i}$.

Proof: Let $i\in[1\ldots n]$ be an index in $S$. Algorithm 3 increases the
value of $R[i]$ by $1$ every time it processes an occurrence
$w_{1}=S[s_{1}\ldots e_{1}]$ of $w^{c}_{l}$ with the following properties:

  1. 1.

$S^{s_{1}}>_{L}S^{s}$

  2. 2.

$max(s_{1}-l,s_{1}-\frac{k}{2})\leq i$

  3. 3.

$\min(e_{1}+r-k+1,s_{1})\geq i$

Recall that Fact 44 suggests that for every dynamic suffix $S^{j}$ with
$j=D(\delta)$ for some $\delta\in[0\ldots\frac{k}{2}]$ such that
$w^{new}_{i}=w^{new}_{j}$ and $S^{j}<_{L}S^{i}$, we have a unique occurrence
of $w^{c}_{l}$ starting in index $i+\delta$. We show that $i$ is increased by
Algorithm 3 when iterating an occurrence $w_{1}$ iff $w_{1}$ is an occurrence
corresponding to one of these dynamic suffixes.

From the second component in the $max$ expression in 2 and 3 we get
$i\in[s_{1}-\frac{k}{2},s_{1}]$. Therefore, we have $s_{1}=i+\delta$ for some
$\delta\in[0\ldots\frac{k}{2}]$. The first expression in 2 yields $l\geq
s_{1}-i$ and therefore $\delta\leq lcs(s_{1}-1,s-1)$. The first expression in
3 yields $r\geq i+k-e_{1}-1$. Since $e_{1}=s_{1}+\frac{k}{2}-1$, we have
$lcp(e_{1}+1,e+1)=r\geq\frac{k}{2}-\delta$. We have shown that $i$ is
increased by Algorithm 3 when processing $w_{1}$ iff an occurrence $w_{1}$
satisfies Proposition 2 of Fact 44 with respect to $i$. This concludes the
proof. ∎

Similarly to Algorithm 1, Algorithm 3 can be easily implemented in time
$O(|occ(w^{c}_{l})|)$. Again, this is not sufficiently efficient. The solution
is the same - we process the periodic occurrences representation of
$w^{c}_{l}$ rather than the explicit occurrences.

Let $C=(a,b,p)$ be a cluster of occurrences $s_{t}=a+t\cdot p$ of $w^{c}_{l}$.
Let $w_{t}=S[s_{t}\ldots e_{t}]$ be the $t$’th occurrence in the cluster $C$.
Let $l_{t}=lcs(s_{t}-1,s-1)$ and $r_{t}=lcp(e_{t}+1,e)$. Let $I_{>}$ be the
interval of $t$ values that satisfies $S^{s_{t}}>_{L}S^{s}$. Let
$i_{t}=max(s_{t}-l_{t},s_{t}-\frac{k}{2})$ and
$j_{t}=\min(e_{t}+r_{t}-k+1,s_{t})$ be the ends of the interval update applied
to $r$ when the occurrence $w_{t}$ is processed in Algorithm 3. We make the
following claim:

######  Claim 46.

Given $C$ and $w=S[s\ldots t]$, all the updates $u_{t}=(i_{t},j_{t},1)$ for
$t\in I_{>}$ can be applied to $R$ in time $O(\log^{3}(n))$.

Proof: Similar to the proof of Claim 42. We start by employing Lemma 36 to
obtain $l_{t}=\min(Ex_{l},Ex^{C}_{l}+p\cdot t)$ and
$r_{t}=\min(Ex_{r},Ex^{C}_{r}-p\cdot t)$ for non-aligned occurrences. ∎

With that, we can prove the following:

######  Claim 47.

For non-aligned occurrences, $\\{i_{t}\\}$ and $\\{j_{t}\\}$ are $p$-normal
sequences with degree $3\in O(1)$.

Proof: By substituting Lemma 36 and $s_{t}=s_{0}+t\cdot p$, we get
$i_{t}=max(s_{0}+p\cdot t-\min(Ex_{l},Ex^{C}_{l}+p\cdot t),s_{0}+p\cdot
t-\frac{k}{2})$. Since $s_{0}-\frac{k}{2}$ is a constant, the second argument
of this max expression is an arithmetic progression with difference $p$. The
first argument can be rewritten as $max(s_{0}+t\cdot
p-Ex_{l},s_{0}-Ex^{C}_{l})$, which is a $p$-normal sequence with degree $2$.
With that, we proved that $\\{i_{t}\\}$ is a $p$-normal sequence with degree
$3$. Similar arguments can be made to show that $\\{j_{t}\\}$ is a $p$-normal
sequence with degree $3$ as well. ∎

It follows from the above claim that applying all the updates corresponding to
non-aligned occurrences can be reduced to applying a constant number of stairs
with stair width $p$ updates and interval increment updates (Lemma 41). The
(at most two) aligned occurrences can be explicitly handled by applying two
interval increment updates in $O(\log(n))$ time. The time for applying a
constant number of stairs and interval increment updates corresponding to the
non-aligned occurrences is bounded by $O(\log^{3}(n))$ ∎

With this, an efficient implementation of Algorithm 3 can be constructed in an
identical manner to the construction of Algorithm 2.

###### Algorithm 4

Obtain the periodic occurrences representation $por$ of $w^{c}_{l}$. For every
singular occurrence $w=S[s_{1}\ldots e_{1}]$ in $por$: 1. Check if
$S^{s_{1}}>_{L}S^{s}$. If it is not, then stop processing this occurrence. 2.
Compute $l=lcs(s_{1}-1,s-1)$ and $r=lcp(e_{1}+1,e+1)$. 3. Increase the
counters of $R$ with indexes in
$[max(s_{1}-l,s_{1}-\frac{k}{2}),\min(e_{1}+r-k+1,s_{1})]$ by $1$ For every
cluster $C=(a,b,c)$ of occurrences in $por$: 1. Obtain $I_{>}$ using Claim 38.
2. Apply to $R$ all the interval updates corresponding to $w_{t}$ with $t\in
I_{>}$ by employing Claim 46.

It is easy to see that Algorithm 4 applies exactly the same updates to $R$ as
Algorithm 3 does. The same arguments as in the proof of Claim 43 can be made
to prove that Algorithm 4 runs in time $\tilde{\mathcal{O}}(\sqrt{n})$. Recall
that Algorithm 4 only counts dynamic suffixes $S^{j}$ with $j\in[x-k+1\ldots
x-\frac{k}{2}]$, and a symmetric procedure needs to be executed for the
remaining dynamic suffixes. This concludes the evaluation of right shifts.

Finally, we need to handle left shifts. For every static suffix $S^{i}$, we
need to count the amount of dynamic suffixes $S^{j}$ for which
$w^{old}_{j}=w^{old}_{i}$ and $T^{j}<_{L}T_{i}$, and subtract that number from
$R[i]$.

This can be executed with an algorithm almost identical to Algorithm 4, with
the following two minor modifications:

  1. 1.

Instead of considering the occurrences of $w^{c}_{l}=S[x-\frac{k}{2}+1\ldots
x]$, consider occurrences of $u^{c}_{l}=T[x-\frac{k}{2}+1\ldots x]$

  2. 2.

Replace every interval and stairs update with its negative variant.

Since we consider the same indexes of $w^{c}_{l}$ in $T$ rather than in $S$,
an occurrence of $u^{c}_{l}$ is extendable to occurrences of $w^{old}_{i}$ in
the same manner as an occurrence of $w^{c}_{l}$ is extendable to occurrences
of $w^{new}_{i}$. Similarly to right shifts, Algorithm 4 with the above
modification would only count dynamic suffixes $S^{j}$ with $j\in[x-k+1\ldots
x-\frac{k}{2}]$, and a symmetric procedure needs to be executed for the
remaining dynamic suffixes.

We conclude this section with the following.

######  Lemma 48.

Upon a substitution update on text $S$, all the shift updates can be applied
to $R$ in time $\tilde{\mathcal{O}}(\sqrt{n})$.

###  5.3 Overtake updates

In order to apply overtake updates to $R$, we need to increase the value of
$R[i]$ by the amount of static suffixes $S^{j}$ for which $T^{i}<_{L}T^{j}$
and $S^{i}>_{L}S^{j}$ ($S^{i}$ overtakes $S^{j}$) and decrease $R[i]$ by the
amount of static suffixes $S^{j}$ for which $T^{i}>_{L}T^{j}$ and
$S^{i}<_{L}S^{j}$ ($S^{j}$ overtakes $S^{i}$). These updates are required for
every $i\in[1\ldots n]$ (excluding dynamic suffixes). For this purpose, we
consider the word $w^{swap}=S[x-k\ldots x-1]$.

We introduce the notations $lcs_{X}(i,j)$ and $lcp_{X}(i,j)$ denoting the
$LCS$ (resp. $LCP$) of the prefixes (resp. suffixes) of string $X$ ending
(resp. starting) in indexes $i$ and $j$ (Until now, we used $lcs$ and $lcp$ to
refer to $lcp_{S}$ and $lcs_{S}$). We present the following lemma:

(We rename the indexes of $w^{swap}$ to $w^{swap}=S[s\ldots e]$ for clearer
presentation)

######  Lemma 49.

Let $S^{i}$ be a static suffix. A static suffix $S^{j}$ overtakes $S^{i}$, iff
one of the following conditions is satisfied.

Condition 1: All of the following sub-conditions are satisfied for
$s_{1}=j+s-i$:

  1. 1.

$s-i\geq 0$

  2. 2.

There is an occurrence $w_{1}=S[s_{1}\ldots e_{1}]$ of $w^{swap}$

  3. 3.

$S^{s_{1}}$ is a static suffix

  4. 4.

$S^{s_{1}}$ overtakes $S^{s}$

  5. 5.

$m(s,s_{1})\geq s-i$.

Condition 2: All of the following sub-conditions are satisfied for
$s_{1}=i+s-j$:

  1. 1.

$s-j\geq 0$

  2. 2.

There is an occurrence $w_{1}=S[s_{1}\ldots e_{1}]$ of $w^{swap}$

  3. 3.

$S^{s_{1}}$ is a static suffix

  4. 4.

$S^{s}$ overtakes $S^{s_{1}}$

  5. 5.

$m(s,s_{1})\geq s-j$.

In both conditions,
$m(s,s_{1})=\min(lcs_{S}(s-1,s_{1}-1),lcs_{T}(s-1,s_{1}-1))$

Lemma 49 may seem technical and involved, but it aims to describe a fairly
straightforward intuition. In a high level, Lemma 49 states that the common
extension to the right of two suffixes $S^{i}$ and $S^{j}$ such that one
overtake the other must reach the substitution index $x$. The common extension
must therefore contain an occurrence $w_{1}$ of $w^{swap}$, and there must be
an overtake between $w^{swap}$ and $w_{1}$. For an example, see Figure 6.

Figure 6: A visualization of Lemma 49. The upper segment is a segment of the
text around the substitution index $x$. The lower segment is a segment of the
text around an occurrence $w_{1}$ of $w^{swap}$. The arrow to the left of
$w_{1}$ denotes the $lcs$ between $w_{1}$ and $w^{swap}$. The indexes $i$ and
$j$ are selected as an arbitrary example for $i$ and $j$ in the statement of
the lemma. Every two aligned indexes within the blue interval would be a valid
demonstration of Lemma 49.

Proof: We start by proving the first direction. Namely, we show that if a
static suffix $S^{j}$ overtakes $S^{i}$, we have an occurrence $w_{1}$
satisfying one of the conditions presented in the Lemma.

Let $r=lcp_{S}(i,j)$ and $r^{\prime}=lcp_{T}(i,j)$. We start by proving the
following claim:

######  Claim 50.

Either $x=i+\min(r^{\prime},r)$ or $x=j+\min(r,r^{\prime})$.

Proof: We assume that $r\leq r^{\prime}$, the case in which $r>r^{\prime}$ can
be treated symmetrically. From the definition of $r$ we have $S[i\ldots
i+r-1]=S[j\ldots j+r-1]$. Since $S^{j}$ overtakes $S^{i}$, we have
$S[i+r]<S[j+r]$. We consider two cases:

  1. 1.

$r=r^{\prime}$. In this case, from the definition of $r^{\prime}$ we have
$T[i\ldots i+r-1]=T[j\ldots j+r-1]$. And from the fact that $S^{j}$ overtakes
$S^{i}$, $T[i+r]>T[j+r]$.

  2. 2.

$r<r^{\prime}$. In this case, we have $T[i\ldots i+r^{\prime}-1]=T[j\ldots
j+r^{\prime}-1]$. Since $r<r^{\prime}$, we must have $T[i+r]=T[j+r]$.

In both cases, the lexicographic order between $T[i+r]$ and $T[j+r]$ is
different from the lexicographic order between $S[i+r]$ and $S[j+r]$.
Therefore, either $T[i+r]$ or $T[j+r]$ is the symbol modified by the
substitution update. ∎

We partition our proof into two cases, depending on which of the options for
the value of $x$ presented in Claim 50 applies.

  1. 1.

$x=i+\min(r,r^{\prime})$. In this case, we show that condition 1 is satisfied.
Since $S^{i}$ is static and $i\leq x$, we must have $i\leq x-k=s$ (sub-
condition 1). Therefore, $S[i\ldots i+\min(r,r^{\prime})-1]$ and $T[i\ldots
i+\min(r,r^{\prime})-1]$ both contain the substring $S[x-k+1\ldots
x-1]=w^{swap}$.

Let $d_{s}$ and $d_{e}$ be two integers such that $i+d_{s}=s$ and $i+d_{e}=e$.
Note that $d_{s}=\min(r,r^{\prime})-k$ and $d_{e}=\min(r,r^{\prime})-1$. Since
$r$ is the longest common prefix of $S^{i}$ and $S^{j}$, we have $S[i\ldots
i+\min(r,r^{\prime})-1]=S[j\ldots j+\min(r,r^{\prime})-1]$. And in particular,
$S[j+d_{s}\ldots j+d_{e}]=S[i+d_{s}\ldots i+d_{e}]=w^{swap}$. Since
$\min(r,r^{\prime})\leq r^{\prime}$, we have equality of the substrings with
the same indexes in $T$. So we have an occurrence of $w^{swap}$ in index
$j+d_{s}$ both in $S$ and in $T$. Denote $s_{1}=j+d_{s}$ and $e_{1}=j+d_{e}$
and $w_{1}=S[s_{1}\ldots e_{1}]$. Note that $s_{1}=j+s-i$, $s_{1}$ is a
starting index of an occurrence of $w^{swap}$ in $S$ (sub-condition 2), and
since $s_{1}$ is a starting index of the same word $w^{swap}$ with length $k$
both in $S$ and in $T$, $S^{s_{1}}$ is a static suffix (sub-condition 3).

From $S[i\ldots i+r-1]=S[j\ldots j+r-1]$ we get $S[i+d_{s}\ldots
i+r-1]=S[j+d_{s}\ldots j+r-1]$. Recall that $S[i+r]<_{L}S[j+r]$. Therefore,
$S^{s}<_{L}S^{s_{1}}$. From $T[i\ldots i+r^{\prime}-1]=T[j\ldots
j+r^{\prime}-1]$ we get $T[i+d_{s}\ldots i+r^{\prime}-1]=T[j+d_{s}\ldots
j+r^{\prime}-1]$ and therefore $T[s\ldots i+r^{\prime}-1]=T[s_{1}\ldots
j+r^{\prime}-1]$. Since $S^{j}$ overtakes $S^{i}$, we have
$T[i+r^{\prime}]>_{L}T[j+r^{\prime}]$ and therefore $T^{s}>_{L}T^{s_{1}}$. We
showed that $T^{s}>_{L}T^{s_{1}}$ and $S^{s}<_{L}S^{s_{1}}$. Therefore,
$S^{s_{1}}$ overtakes $S^{s}$ (sub-condition 4). Since $S[i\ldots s]=S[j\ldots
s_{1}]$ and $T[i\ldots s]=T[j\ldots s_{1}]$ we have
$m(s,s_{1})=\min(lcs_{S}(s-1,s_{1}-1),lcs_{T}(s-1,s_{1}-1))\geq s-i$.

  2. 2.

$x=j+\min(r,r^{\prime})$. Symmetrical arguments can be made to show that in
this case, condition 2 is satisfied.

We proceed to prove the second direction of the lemma. Namely, if there is an
occurrence $w_{1}=S[s_{1}\ldots e_{1}]$ of $w^{swap}=S[s\ldots e]$ satisfying
one of the conditions in the statement of the Lemma, $S^{j}$ overtakes
$S^{i}$. We provide a proof for the first condition. A proof for the second
condition can be constructed in a similar manner.

Assume that condition 1 holds, so we have $s-i\geq 0$ , and an occurrence
$w_{1}=S[s_{1}\ldots e_{1}]$ of $w^{swap}$ such that $s_{1}=j+s-i$. We also
know that $S^{s_{1}}$ is a static suffix overtaking $S^{s}$ and
$m(s,s_{1})\geq s-i$.

From the definition of $m(s,s_{1})$ we have:

  1. 1.

$S[s_{1}-m(s,s_{1})\ldots s_{1}-1]=S[s-m(s,s_{1})\ldots s-1]$

  2. 2.

$T[s_{1}-m(s,s_{1})\ldots s_{1}-1]=T[s-m(s,s_{1})\ldots s-1]$

Since $m(s,s_{1})\geq s-i\geq 0$, the above particularly implies:

  1. 1.

$S[j\ldots s_{1}-1]=S[i\ldots s-1]$

  2. 2.

$T[j\ldots s_{1}-1]=T[i\ldots s-1]$

Let $r=lcp_{S}(s,s_{1})$ and $r^{\prime}=lcp_{T}(s,s_{1})$. From the
definitions of $r$ and $r^{\prime}$ we have $S[s\ldots
s+r-1]=S[s^{\prime}\ldots s^{\prime}+r-1]$ and $T[s\ldots
s+r^{\prime}-1]=T[s_{1}\ldots s_{1}+r^{\prime}-1]$. Putting it together with
the above, we get:

  1. 1.

$S[j\ldots s_{1}+r-1]=S[i\ldots s+r-1]$

  2. 2.

$T[j\ldots s_{1}+r^{\prime}-1]=T[i\ldots s+r^{\prime}-1]$

Since $S^{s_{1}}$ is a static suffix overtaking $S^{s}$, we have
$S[s_{1}+r]>S[s+r]$ and $T[s_{1}+r^{\prime}]<T[s+r^{\prime}]$. Therefore,
$S^{j}$ overtakes $S^{i}$. ∎

Given two static suffixes $S^{i}$ and $S^{j}$ such that $S^{j}$ overtakes
$S^{i}$, we say that an occurrence of $w^{swap}$ satisfying one of the
conditions of Lemma 49 with respect to $S^{i}$ and $S^{j}$ is implying the
overtake between $S^{j}$ and $S^{i}$. The following Lemma is required to
ensure that we count every overtake exactly once.

######  Lemma 51.

Given two static suffixes $S^{i}$ and $S^{j}$ such that $S^{j}$ overtakes
$S^{i}$, there is exactly one occurrence $w_{1}$ of $w^{swap}$ implying the
overtake between $S^{j}$ and $S^{i}$.

Proof: The existence of at least one implying occurrence is immediate from
Lemma 49. Given $i$, $j$ and $s$, there are only two possible starting indexes
for the starting index of $w_{1}$: $s_{1}=j+s-i$ and $s_{2}=i+s-j$. Assume to
the contrary that both $s_{1}$ and $s_{2}$ are starting indexes of an
occurrence of $w^{swap}$ satisfying the first and the second conditions in
Lemma 49 respectively.

Let $d=i-j$. Note that $s_{1}=s-d$ and $s_{2}=s+d$. Therefore, one of the
indexes $s_{1}$, $s_{2}$ is to the right of $s$. We assume that $s_{1}>s$, the
case in which $s_{2}>s$ can be treated in a similar way. Since $s_{1}$ is to
the right of $s=x-k$, and is the starting index of a static suffix, it must be
the case that $s_{1}>x$.

Since both of the conditions of Lemma 49 hold, we have $s-i\geq 0$ and
$j-s\geq 0$. Therefore, both $i$ and $j$ are not to the right of $s$. Since
$m(s,s_{1})\geq s-i$ we have the following:

  1. 1.

$S[j\ldots s_{1}-1]=S[i\ldots s-1]$

  2. 2.

$T[j\ldots s_{1}-1]=T[i\ldots s-1]$

Recall that $s_{1}>x$ and $j<s<x$. Therefore, $x\in[j\ldots s_{1}-1]$. Since
$x$ is the modified index, $T[x]\neq S[x]$. In particular, $T[j\ldots
s_{1}-1]\neq S[j\ldots s_{1}-1]$ and it can not be the case that both (1) and
(2) hold. Therefore, we have reached a contradiction. ∎

Lemmas 49 and 51 enable the construction of an algorithm with the structure of
Algorithms 1 \- 4. It allows us to identify overtake updates using the
occurrences of $w^{swap}$ in a similar manner to how we use Fact 44 to
identify shift updates using occurrences of $w^{c}_{l}$.

As before, we start by showing an inefficient algorithm for the sake of
presenting the modifications that are required to be applied to $R$ in order
to represent the overtake updates corresponding to an individual occurrence of
$w^{swap}$. We present Algorithm 5.

###### Algorithm 5

For every occurrence $w=S[s_{1}\ldots e_{1}]$ of $w^{swap}$: 1. If $S^{s_{1}}$
is a dynamic suffix - stop processing $S^{s_{1}}$ 2. If $S^{s_{1}}<_{L}S^{s}$
and $T^{s_{1}}>_{L}T^{s}$ ($S^{s}$ overtakes $S^{s_{1}}$) (a) Compute
$l_{S}=lcs_{S}(s_{1}-1,s-1)$ and $l_{T}=lcs_{T}(s_{1}-1,s-1)$. (b) Increase
the counters of $R$ with indexes in $[s-\min(l_{S},l_{T}),s]$ by $1$. (c)
Decrease the counters of $R$ with indexes in $[s_{1}-\min(l_{S},l_{T}),s_{1}]$
by $1$ 3. If $S^{s_{1}}>_{L}S^{s}$ and $T^{s_{1}}<_{L}T^{s}$ ($S^{s_{1}}$
overtakes $S^{s}$) (a) Compute $l_{S}=lcs_{S}(s_{1}-1,s-1)$ and
$l_{T}=lcs_{T}(s_{1}-1,s-1)$. (b) Decrease the counters of $R$ with indexes in
$[s-\min(l_{S},l_{T}),s]$ by $1$. (c) Increase the counters of $R$ with
indexes in $[s_{1}-\min(l_{S},l_{T}),s_{1}]$ by $1$

We start by proving that Algorithm 5 applies overtake updates correctly.

######  Lemma 52.

For every $i\in[1\ldots n]$, let $\uparrow^{i}$ be the number of times that
$R[i]$ is increased during the execution of Algorithm 5. Let $\downarrow^{i}$
be the number of times that $R[i]$ is decreased during the execution of
Algorithm 5. $\uparrow^{i}$ equals to the number of suffixes $S^{j}$ that
$S^{i}$ is overtaking. $\downarrow^{i}$ equals to the amount of suffixes
$S^{j}$ that are overtaking $S^{i}$.

Proof: Let $j\in[1\ldots n]$ be an index (we use $j$ instead of $i$ in order
to be consistent with the statement of Lemma 49). $R[j]$ is increased in step
2b (second ’if’) every time an iterated occurrence $w_{1}=S[s_{1}\ldots
e_{1}]$ of $w^{swap}$ satisfies the following conditions:

  1. 1.

$S^{s_{1}}$ is static.

  2. 2.

$S^{s}$ overtakes $S^{s_{1}}$

  3. 3.

$j\leq s$

  4. 4.

$j\geq s-\min(lcs_{S}(s_{1}-1,s-1),lcs_{T}(s_{1}-1,s-1))$

Let $i=s_{1}-s+j$. It can be easily verified that all the sub-conditions of
Condition 2 of Lemma 49 are satisfied for $s_{1}$, making $w_{1}$ a unique
occurrence implying that $S^{j}$ overtakes $S^{i}$.

An index $j$ is increased in step 3c (third ’if’) every time an iterated
occurrence $w_{1}=S[s_{1}\ldots e_{1}]$ satisfies the following conditions:

  1. 1.

$S^{s_{1}}$ is static.

  2. 2.

$S^{s_{1}}$ overtakes $S^{s}$.

  3. 3.

$j\leq s_{1}$

  4. 4.

$j\geq s_{1}-\min(lcs_{S}(s_{1}-1,s-1),lcs_{T}(s_{1}-1,s-1))$

Let $i=s-s_{1}+j$. It can be easily verified that all the sub-conditions of
condition 1 of Lemma 49 are satisfied for $s_{1}$, making $w_{1}$ a unique
occurrence implying that $S^{j}$ overtakes $S^{i}$.

Lemma 51 guarantees that every suffix $S^{i}$ such that $S^{j}$ overtakes
$S^{i}$ corresponds to a unique occurrence of $w^{swap}$ satisfying one of the
above conditions. It directly follows that $\uparrow^{j}$ is exactly the
amount of suffixes overtaken by $S^{j}$.

Symmetrical arguments can be made to show the $\downarrow^{i}$ is equal to the
amount of suffixes that overtake $S^{i}$. ∎

As in evaluation and shift updates, a straightforward implementation of
Algorithm 5 is not efficient. In order to implement Algorithm 5 efficiently,
we need the following claims:

######  Claim 53.

Let $C=(a,b,p)$ be a cluster of occurrences of a word $w=S[s\ldots e]$ with
the $t$’th occurrence represented by $C$ denoted as $w_{t}=S[s_{t}\ldots
e_{t}]$. There are consecutive intervals $I^{\uparrow}$ and $I^{\downarrow}$
such that $S^{s_{t}}$ overtakes $S^{s}$ iff $t\in I^{\uparrow}$ and $S^{s}$
overtakes $S^{s_{t}}$ iff $t\in I^{\downarrow}$. The intervals $I^{\uparrow}$
and $I^{\downarrow}$ can be found in $O(\log(n))$ time.

Proof: We can apply Claim 38 to find the intervals $I^{S}_{>}=[i_{1}\ldots
j_{1}]$ and $I^{T}_{<}=[i_{2}\ldots j_{2}]$ such that $S^{s_{t}}>_{L}S^{s}$
iff $t\in I^{S}_{>}$ and $T^{s_{t}}<_{L}T^{s}$ iff $t\in I^{T}_{<}$. By
definition, $I^{\uparrow}=I^{S}_{>}\cap
I^{T}_{<}=[max(i_{1},i_{2})\ldots\min(j_{1},j_{2})]$. We can apply Claim 38 to
find the intervals $I^{S}_{<}=[i_{3}\ldots j_{3}]$ and $I^{T}_{>}=[i_{4}\ldots
j_{4}]$ such that $S^{s_{t}}<_{L}S^{s}$ iff $t\in I^{S}_{<}$ and
$T^{s_{t}}>_{L}T^{s}$ iff $t\in I^{T}_{>}$. By definition,
$I^{\downarrow}=I^{S}_{<}\cap
I^{T}_{>}=[max(i_{3},i_{4})\ldots\min(j_{3},j_{4})]$. ∎

We need to further ’filter’ the occurrences represented by a cluster to
exclude dynamic suffixes. We employ the following simple claim.

######  Claim 54.

Let $I=[i\ldots j]$ be a subinterval of $[0\ldots|C|-1]$ representing a subset
of the indexes of the occurrences implied by a cluster $C$. $I$ can be
processed in $O(1)$ time to evaluate at most two subintervals $I_{1}$ and
$I_{2}$ such that $t\in I_{1}\cup I_{2}$ iff $S^{s_{t}}$ is a static suffix
and $t\in I$.

Proof: We need to find the maximal value $t_{1}$ in $I$ such that
$s_{t_{1}}\leq x-k$ and the minimal value $t_{2}$ such that $s_{t_{2}}\geq
x+1$. Straightforwardly, $I_{1}=[i\ldots t_{1}]$ and $I_{2}=[t_{2}\ldots j]$
satisfy the desired condition. Since $s_{t}$ is given as an arithmetic
progression, $t_{1}$ and $t_{2}$ can be found in constant time. ∎

We adopt the notations of $I^{\uparrow}$ and $I^{\downarrow}$ from Claim 53
for the following claim. we also present the notation
$I^{1}_{st}=[i^{1}_{st}\ldots j^{1}_{st}]$ and $I^{2}_{st}=[i^{2}_{st}\ldots
j^{2}_{st}]$ denoting the intervals of indexes within $[0\ldots|C|-1]$
corresponding to static suffixes.

Let $C=(a,b,p)$ be a cluster of occurrences of $w^{swap}=S[s\ldots e]$ with
the $t$’th occurrence represented by $C$ denoted as $w_{t}=S[s_{t}\ldots
e_{t}]$. We employ the notations $l^{S}_{t}=lcs_{S}(s-1,s_{t}-1)$ and
$l^{T}_{t}=lcp_{T}(e+1,e_{t}+1)$. For $t\in I^{\downarrow}\cap(I^{1}_{st}\cup
I^{2}_{st})$, we define the following sequences of interval increment updates:

  * •

$u^{1}_{t}=(i^{1}_{t}\ldots j^{1}_{t},1)=(s-\min(l^{S}_{t},l^{P}_{t}),s,1)$
the interval increment update applied to $R$ when $w_{t}$ is processed in step
2b of Algorithm 5.

  * •

$u^{2}_{t}=(i^{2}_{t},j^{2}_{t},-1)=(s_{t}-\min(l^{S}_{t},l^{P}_{t}),s_{t},-1)$
the (negative) interval increment applied to $R$ when $w_{t}$ is processed in
step 2c of Algorithm 5

For $t\in I^{\uparrow}\cap(I^{1}_{st}\cup I^{2}_{st})$, we define the
following sequences of interval increment updates:

  * •

$u^{3}_{t}=(i^{3}_{t}\ldots j^{3}_{t},1)=(s-\min(l^{S}_{t},l^{P}_{t}),s,1)$
the interval increment update applied to $R$ when $w_{t}$ is processed in step
3b of Algorithm 5.

  * •

$u^{4}_{t}=(i^{4}_{t}\ldots
j^{4}_{t},-1)=(s_{t}-\min(l^{S}_{t},l^{P}_{t}),s_{t},-1)$ the (negative)
interval increment update applied to $R$ when $w_{t}$ is processed in step 3c
of Algorithm 5.

We make the following claim.

######  Claim 55.

Given $C$ and $w=S[s\ldots t]$, all the updates $u^{y}_{t}$ for $t\in
I^{\downarrow}\cap(I^{1}_{st}\cup I^{2}_{st})$ and $y\in\\{1,2\\}$ can be
applied to $R$ in time $O(\log^{3}(n))$. All the updates $u^{y}_{t}$ for $t\in
I^{\uparrow}\cap(I^{1}_{st}\cup I^{2}_{st})$ and $y\in\\{3,4\\}$ can be
applied to $R$ in time $O(\log^{3}(n))$

Proof: As in the proof of Claim 42, we start by applying Lemma 36 to obtain
$l_{t}=\min(Ex_{l},Ex^{C}_{l}+p\cdot t)$ for non-aligned occurrences $w_{t}$.
We proceed to prove the following claim:

######  Claim 56.

$i^{2}_{t}$ is a $p$-normal sequence with degree $4$ for non-aligned
occurrences.

Proof: By Lemma 36, both $l^{S}_{t}$ and $l^{T}_{t}$ can be written as
$l^{S}_{t}=\min(f_{S},a_{S}+t\cdot p)$ and $l^{T}_{t}=\min(f_{T},a_{T}+t\cdot
p)$ for some constants $f_{S}$, $f_{T}$, $a_{S}$ and $a_{T}$ for non-aligned
occurrences. Therefore, $i^{2}_{t}=s_{0}+t\cdot p-\min(\min(f_{T},a_{T}+t\cdot
p),\min(f_{S},a_{S}+t\cdot p))$ . It follows that
$i^{2}_{t}=max(max(s_{0}+t\cdot p-f_{T},s_{0}-a_{T}),max(s_{0}+t\cdot
p-f_{S},s_{0}-a_{S}))$. This is a $p$-normal sequence with degree $4$. ∎

It can be easily proven that $i^{z}_{t}$ and $j^{z}_{t}$, excluding aligned
occurrences, are $p$-normal sequences with constant degrees for every
$z\in[1\ldots 4]$ by applying the same reasoning.

We apply Lemma 41 in the same manner as in the proof of Claim 42 to obtain a
constant number of interval and stairs updates that are equivalent to applying
all the updates corresponding to non-aligned occurrences. Note that we need to
treat $I^{\downarrow}\cap I^{1}_{st}$ and $I^{\downarrow}\cap I^{2}_{st}$
independently, as 41 deals with a consecutive $p$-normal sequence. Applying
the constant set of stairs updates and interval increment updates can be
executed in $O(\log^{3}(n))$ time. The (at most two) updates corresponding to
aligned occurrences can be applied to $R$ in $O(\log(n))$ time by employing
Claim 33. ∎

With Claim 53, Claim 54 and Claim 55, we are ready to present the efficient
variant of Algorithm 5.

###### Algorithm 6

Obtain the periodic occurrences representation $por$ of $w^{swap}$: For every
singular occurrence $w=S[s_{1}\ldots e_{1}]$ in $por$: Process $w_{1}$ as in
Algorithm 5. For every cluster of occurrence $C=(a,b,p)$ in $por$: Obtain
$I^{\uparrow}_{st}=I^{\uparrow}\cap(I^{1}_{st}\cup I^{2}_{st})$ and
$I^{\downarrow}_{st}=I^{\downarrow}\cap(I^{1}_{st}\cup I^{2}_{st})$ using
Claims 53 and 54. If $I^{\uparrow}_{st}$ is not empty: Efficiently apply the
interval updates corresponding to $w^{t}$ with $t\in I^{\uparrow}$ using Claim
55. If $I^{\downarrow}_{st}$ is not empty: Efficiently apply the interval
updates corresponding to $w^{t}$ with $t\in I^{\downarrow}$ using Claim 55.

It is straightforward that Algorithm 6 applies the same updates to $R$ as
Algorithm 5 does - as it only processes occurrences corresponding to static
suffixes that either overtake $S^{s}$ or are overtaken by $S^{s}$. We conclude
this section with the following.

######  Lemma 57.

Upon a substitution update in index $x$ of $S[1\ldots n]$. All the overtake
update can be applied to $R$ in $\tilde{\mathcal{O}}(\sqrt{n})$ time.

Proof: Applying Algorithm 6 results in the same changes to $R$ as applying
Algorithm 5. This is equivalent to applying the overtake updates according to
Lemma 52. Algorithm 6 processes every singular occurrence or cluster in the
periodic occurrences representation of $w^{swap}$ in polylogarithmic time.
Therefore, it runs in time
$\tilde{\mathcal{O}}(\frac{n}{k})=\tilde{\mathcal{O}}(\sqrt{n})$ ∎.

Recall that for shift and overtake updates we manipulate the existing ranks in
$R$ by applying interval increment and stairs updates to $R$, but for
evaluation we set the updated ranks explicitly. Therefore, shifts and overtake
modification needs to be counted and applied to $R$ prior to the evaluation of
the ranks of dynamic suffixes. This is required to avoid the case in which a
rank is set for a dynamic suffix, and then modified by a stairs or an interval
update.

With that, we have shown how to efficiently apply every type of updates to
$R$. Upon a substitution update to $S$ in index $x$, we apply algorithms 2, 4
and 6 to update $R[i]$. After doing so, $R[i]$ contains the updated close
suffix rank of $S^{i}$, for every $i\in[1\ldots n]$.

###  5.4 Handling Stairs Updates

In this section, we show how to apply the restricted data structure provided
by Theorem 2 to our settings. We recall that the data structure of Theorem 2
enables the application of a stairs update to a set of counters and an
evaluation of a counter in polylogarithmic time, but only if every stairs
update $(i,j,p)$ has the same stair width $p$.

Our dynamic algorithm require stairs update with various values of $p$, so the
data structure of Theorem 2 is not sufficient. We start by showing that for
every stairs update $(i,j,p)$ that is applied by our algorithm, $S[i\ldots j]$
is periodic. We then proceed to show how this property, alongside with the
restricted stairs updates data structure, can be used to efficiently support
stairs updates in our settings.

We start with the following observations concerning the structure of the
interval updates applied in Algorithm 3 and in Algorithm 5.

######  Observation 58.

Let $C=(a,b,p)$ be a cluster of occurrences of a word $w^{c}_{l}=S[s\ldots e]$
with period $p$ that is processed in Algorithm 3. Let $R_{C}=S[i_{C}\ldots
j_{C}]$ be the run with period $p$ containing the occurrences implied by $C$.
For an occurrence $w_{t}=S[s_{t}\ldots e_{t}]$ implied by $C$, let
$u_{t}=(i_{t},j_{t},1)$ be the interval increment update applied to $R$ when
$w_{t}$ is processed by Algorithm 3. Every occurrence $w_{t}$ implied by $C$
that is not an aligned occurrence has $[i_{t}\ldots
j_{t}]\subseteq[i_{C}\ldots j_{C}]$.

Proof: In algorithm 3, the left border of the interval update applied to an
occurrence $w_{t}$ of $w^{c}_{l}$ is
$i_{t}=max(s_{t}-l_{t},s_{t}-\frac{k}{2})$. The right border of the update is
$j_{t}=\min(e_{t}+r_{t}-k+1,s_{t})$. According to Lemma 36, for an occurrence
that is not aligned we have $i_{t}=max(s_{t}-\min(Ex_{l},Ex^{C}_{l}+p\cdot
t),s_{t}-\frac{k}{2})$ which is at least $s_{t}-\min(Ex_{l},Ex^{C}_{l}+p\cdot
t)\geq s_{t}-Ex^{C}_{l}-p\cdot t=s_{0}-Ex^{C}_{l}=i_{C}$.

According to Lemma 36, we have $j_{t}=\min(e_{t}+\min(Ex_{r},Ex^{C}_{r}-p\cdot
t)-k+1,s_{t})\leq s_{t}$. Since all the occurrences implied by $C$ are
contained within $R_{C}$, we have $s_{t}\leq j_{C}$ and therefore $j_{t}\leq
j_{C}$. We showed that $i_{t}\geq i_{C}$ and $j_{t}\leq j_{C}$. Therefore,
$[i_{t}\ldots j_{t}]\subseteq[i_{C}\ldots j_{C}]$. ∎

We proceed with a similar observation concerning Algorithm 5.

######  Observation 59.

Let $C=(a,b,p)$ be a cluster of occurrences of a word $w^{swap}=S[s\ldots e]$
with period $p$ that is processed in Algorithm 5. Let $Run_{C}=S[i_{C}\ldots
j_{C}]$ and $Run_{w}=S[i_{w}\ldots j_{w}]$ be the runs with period $p$
containing the occurrences implied by $C$ and the word $w^{swap}$,
respectively. For an occurrence $w_{t}=S[s_{t}\ldots e_{t}]$ implied by $C$,
let $u_{1}$, $u_{2}$, $u_{3}$ and $u_{4}$ be the interval increment update
applied to $R$ when $w_{t}$ is processed by Algorithm 5 in step 2b, step 2c,
step 3b and step 3c, respectively. Let $u^{z}_{t}=(i^{z}_{t},j^{z}_{t},b_{z})$
for $z\in[1\ldots 4]$ and $b_{z}\in\\{1,-1\\}$. The following holds:

  1. 1.

for $z=1$ and $z=3$, every non-aligned occurrence $u_{t}$ has
$[i^{z}_{t},j^{z}_{t}]\subseteq[i_{w}\ldots j_{w}]$.

  2. 2.

for $z=2$ and $z=4$, every non-aligned occurrence $u_{t}$ has
$[i^{z}_{t},j^{z}_{t}]\subseteq[i_{C}\ldots j_{C}]$.

Proof: For $z=2$ and $z=4$, the left border of the interval update applied to
an occurrence $w_{t}$ of $w^{swap}$ in step 2b in both parts is
$i^{2}_{t}=i^{4}_{t}=s_{t}-\min(l^{S}_{t},l^{T}_{t})\geq s_{t}-l_{t}$ and the
right border is $j^{2}_{t}=j^{4}_{t}=s_{t}$. We showed that $s_{t}-l_{t}\geq
i_{C}$ and $s_{t}\leq j_{C}$ for a non-aligned occurrence in the proof of
Observation 58. So in this case, $[i^{z}_{t}\ldots
j^{z}_{t}]\subseteq[i_{C}\ldots j_{C}]$.

For $z=1$ and $z=3$, the left border of the interval update applied to an
occurrence $w_{t}$ of $w^{swap}$ is in step 2b in both parts is
$i^{1}_{t}=i^{3}_{t}=s-\min(l^{S}_{t},l^{T}_{t})\geq s-l_{t}$ and the right
border $j^{1}_{t}=j^{3}_{t}=s$. Since the run $Run_{w}$ contains $w^{swap}$,
we have $j_{w}\geq e>s$. According to Lemma 36, if $w_{t}$ is not an aligned
occurrence we have $i_{t}\geq s-\min(Ex_{l},Ex^{C}_{l}+p\cdot t)\geq
s-Ex_{l}=i_{w}$. Therefore, we have $[i^{z}_{t}\ldots
j^{z}_{t}]\subseteq[i_{w}\ldots j_{w}]$ ∎.

The following is directly derived from Observations 58 and 59

######  Lemma 60.

For every stairs update $(i,j,p)$ applied by Algorithm 4 or by Algorithm 6,
$S[i\ldots j]$ is contained within a run with period $p$. Either $Run_{w}$ or
$Run_{C}$.

Proof: Recall that we only use stairs updates to apply interval increment
updates corresponding to non-aligned occurrences.

Let $C$ be a cluster of occurrences of a word $w$ with period $p$. Let $U$ be
the set of intervals updates $U$ that are applied to $R$ when the occurrences
implied by $C$ are processed either in algorithm 3, or in one of the steps in
Algorithm 5 in which an interval increment update is applied. In the proofs of
Claims 46 and 55, we show that for non-aligned occurrences, $U$ is a
$p$-normal sequence with a constant degree, and therefore can be reduced to a
constant sized set $St$ of stairs updates with stair width $|p|=p$.

According to Observations 58 and 59, either interval update $u=(i,j,1)\in U$
has $[i\ldots j]\subseteq[i_{C}\ldots j_{C}]$ or every $u\in U$ has $[i\ldots
j]\subseteq[i_{w}\ldots j_{w}]$. Naturally, every stairs update
$(i_{1},j_{1},p)\in St$ has $[i_{1}\ldots j_{1}]\subseteq[i_{C}\ldots j_{C}]$
or $[i_{1}\ldots j_{1}]\subseteq[i_{w}\ldots j_{w}]$. That is due to the fact
that applying these stairs updates is equivalent to applying $U$ and therefore
they only affects the indexes that are affected by the updates in $U$.

To be more precise, it is theoretically possible that $St$ contains stairs
updates that affect an index $i$ that was not modified by the updates in $U$,
and the updates in $St$ cancel each other in index $i$. An examination of
Lemma 106 in Section 8 (in which the method for reducing a sequence of
interval increment updates to a small set of stairs updates and interval
updates is presented) easily shows that this is never the case. ∎

Recall that in every stairs update $(i,j,p)$ applied by our algorithm, $p$ is
the period of a word with length at most $k$. The following directly follows.

######  Observation 61.

Every stairs update $(i,j,p)$ applied by our algorithm has
$p\in[1\ldots\frac{k}{2}]$

We proceed to show how to use the restricted data structure to maintain stairs
updates with various stair widths in our settings.

The idea: We only apply interval increment updates directly to $R$.
Additionally to $R$, we maintain a restricted data structure $St_{p}$ for
applying and querying stairs updates with fixed stair width $p$ for
$p\in[1\ldots\frac{k}{2}]$. We also keep a data structure $ActInt$ for
2-dimensional range searching queries. When we wish to apply a stairs update
$(i,j,p)$ to $R$, we apply it to $St_{p}$ instead. Additionally, we add a
point $(i,j)$ with value $v(i,j)=p$ to $ActInt$. This point represent the
interval $[i\ldots j]$ that was affected by the stairs update. Upon a query
for the close suffixes rank of $S^{i}$, we extract from $ActInt$ the intervals
touching the index $i$. The values of the extracted points form the set $P$ of
values of $p$ such that $St_{p}$ received an update affecting index $i$. We
evaluate $\Sigma_{P}=\Sigma_{p\in P}St_{p}[i]$ and report $\Sigma_{p}+R[i]$.
The periodicity of the intervals that are affected by $St_{p}$ ensures that
$|P|\in O(\log(n))$, so the process of reporting the rank of $S^{i}$ remains
polylogarithmic. However, further work needs to be dedicated to the
maintenance of these intervals and their periodicity properties.

We present the notation of an extremely periodic string.

######  Definition 62.

A string $S$ is extremely periodic if $per(S)\leq\frac{|S|}{5}$

We are interested in runs of $S$ that are also extremely periodic. The
following property of extremely periodic runs of a string $S$ is proven in
Section 6

######  Theorem 63.

Given a string $S[1\ldots n]$, let $x\in[1\ldots n]$ be an index within $S$.
There are $O(\log(n))$ extremely periodic runs containing $x$.

We start by slightly modifying algorithms 4 and 6. Specifically, we replace
some of the stairs updates applied in these algorithms with the set of
interval update they represent. We only do that in a situation in which there
are not many such interval updates, so applying them explicitly is not too
costly. The details for this adjustment are as follows.

Let $w$ be a word we process in one of our algorithms for modifying the ranks
($w^{c}_{l}$, $w^{swap}$, etc). Let $Run_{w}=S[s_{rw}\ldots e_{rw}]$ the run
with period $p$ containing $w$. If $Run_{w}$ is not extremely periodic, it
must be the case that $\frac{|w|}{5}<per(w)$. If that is the case, there are
at most $5\cdot\frac{n}{|w|}\in O(\frac{n}{k})=O(\sqrt{n})$ occurrences of $w$
in $S$ ( [6], Fact 5). We can afford to process them explicitly and apply the
interval increment updates corresponding to them rather than using stairs
updates (as in algorithms 3 and 5).

Otherwise, assume that we process the cluster $C$ of occurrences of $w$. Let
$R_{C}=S[s_{r}\ldots e_{r}]$ be the run with period $p$ containing $C$. Assume
that we need to apply a stairs update $(i,j,p)$ corresponding to a subset of
the occurrences within $C$ such that $S[i\ldots j]$ is contained within the
run $R_{C}$. We check if $R_{C}$ is extremely periodic. If it is not - there
are at most $4$ occurrences of $w$ in $C$. We apply the interval increment
updates derived from these occurrences to $R$ instead of processing them as
stairs updates.

If $R_{C}$ is extremely periodic, we apply the stair update as follows. We add
the point $p_{R_{C}}=(s_{r},e_{r})$ with value $v(p_{R_{C}})=p$ to $ActInt$
(while avoiding duplicates), and apply the stairs update $(i,j,p)$ to
$St_{p}$. If $S[i\ldots j]$ is contained within $RUN_{w}$, we add the point
$p_{w}=(s_{rw},e_{rw})$ with the same value $v(p_{w})=p$ instead of
$p_{R_{c}}$.

######  Observation 64.

With the above modifications, the running times of algorithms 4 and 6 remains
$\tilde{\mathcal{O}}(\sqrt{n})$. For every $i\in[1\ldots n]$, the
modifications applied to $R[i]$ by Algorithm 4 and Algorithm 6 prior to these
modifications are equivalent to the updates applied to
$R[i]+\Sigma_{p=1}^{\frac{k}{2}}St_{p}[i]$ with the modifications.

At this point, it may seem like we are done. We only insert extremely periodic
runs to $ActInt$, so according to Theorem 63 every index $i\in[1\ldots n]$ is
only touched by $O(\log(n))$ runs in $ActInt$. Upon a query for the close
suffix rank of $S^{i}$, we can find all the runs in $ActInt$ containing $i$,
sum $\Sigma_{p}$ the values of $St_{p}[i]$ with the corresponding $p$ values,
and return $\Sigma_{p}+R[i]$. However, there is another subtle point to
handle. The intervals $S[s_{r}\ldots e_{r}]$ such that $(s_{r},e_{r})$ is
inserted to $ActInt$ are extremely periodic runs in the time of their
insertion. Future updates may change that by cutting an extremely periodic run
or by extending it.

Therefore, we need to dedicate some extra work to maintain the following two
invariants:

  1. 1.

Every interval (represented as a point) within $ActInt$ is an extremely
periodic run

  2. 2.

If $x$ is not contained in interval (represented as point) $p_{1}=[s_{1}\ldots
e_{1}]$ with value $p$, we have $St_{p}[x]=0$.

######  Lemma 65.

After a substitution in index $x$, the data structures $ActInt$ and
$\\{St_{p}\\}_{p\in[1\ldots\frac{k}{2}]}$ can be updated such that the above
invariants are preserved, and the accumulated value of
$R[i]+\Sigma_{p=1}^{\frac{k}{2}}St_{p}[i]$ is not affected for every
$i\in[1\ldots n]$. The update can be executed in
$\tilde{\mathcal{O}}(\sqrt{n})$ time.

Proof: Upon an update in index $x$, we assume that the invariants are
satisfied prior to the application of the substitution update in $x$. we query
$ActInt$ for all the intervals containing the index $x$ we get a set
$P^{\prime}$ of points $p_{1}=(s_{1},e_{1})$ such that $S[s_{1}\ldots e_{1}]$
was an extremely periodic run with period $v(p_{1})$ in $T$. Therefore,
according to Theorem 63, $|P^{\prime}|\in O(\log(n))$.

For every point $p_{1}=(s_{1},e_{1})\in P^{\prime}$ with $v(p_{1})=p$, we
initialize a set $Exclude_{p_{1}}=\\{x\\}$ of candidates for exclusion. The
update in $x$ cuts the run $T[s_{1}\ldots e_{1}]$ into two maximal substrings
with period $p$ \- $R_{l}=S[s_{1}\ldots x-1]$ and $R_{r}=S[x+1\ldots e_{1}]$.
We start by deleting $p_{1}$ from $ActInt$. If $|R_{l}|\geq 5\cdot p$ , we
insert $p_{l}=[s_{1}\ldots x-1]$ with $v(p_{l})=p$ to $ActInt$. Otherwise, we
insert the indexes $[s_{1}\ldots x-1]$ to $Exclude_{p_{1}}$ (And do not add
$p_{l}$ to $ActInt$). We treat $R_{r}$ the same.

We proceed to treat the candidates for exclusion. For every index $i\in
Exclude_{p_{1}}$, we check if there is an interval $p_{2}$ in $ActInt$
containing $i$ with $v(p_{2})=p$. If there is a point with that property - we
simply proceed to the next index. If there is not - we evaluate the current
value $a=St_{p}[i]$, set $R[i]=R[i]+a$ and set $St_{p}[i]=0$. By doing that,
we ensure that the value of $St_{p}$ is no longer required for computing the
rank of $S^{i}$ (second variant), while not changing the value of
$R[i]+\Sigma_{p=1}^{\frac{k}{2}}St_{p}[i]$.

We also query $ActInt$ for intervals starting with $x+1$ or ending with $x-1$.
The extremely periodic runs corresponding to these intervals may have been
extended as a result of the update. For every point $p_{1}=(s_{1},x-1)$ with
$v(p_{1})=p$, we query $r=lcp(x-1,x-1-p)$. If $r>0$ \- the run $S[s_{1},x-1]$
was extended. In this case, we remove $p_{1}$ from $ActInt$ and add
$p_{2}=(s_{1},x-1+r)$ instead (while avoiding duplicates). We do the symmetric
procedure for every point $p_{1}=(x+1,e_{1})$.

Complexity: The bottleneck of maintaining the runs within $ActInt$ is the
exclusion procedure. Apart from the exclusion, we use a constant number of
$lcp$, $lcs$, basic arithmetic operations and range queries to $ActInt$ for
every point. Since there are $O(\log(n))$ points touching $x$, $x-1$ and
$x+1$, this is polylogarithmic. We note that the data structure for
maintaining and querying stairs updates can be easily modified to allow
setting a certain index to $0$ without hurting its performance.

As for the exclusion, we only exclude an interval of indexes if its size is
less than $5\cdot p\leq\frac{5k}{2}\in O(k)=O(\sqrt{n})$. We exclude at most
two such intervals for every contested point $p_{1}$, so $|Exclude_{p_{1}}|\in
O(\sqrt{n})$. For every $i\in Exclude_{p_{1}}$, we query $ActInt$ at most
twice and execute a constant number of queries on $St_{p}$ and $R$, all
polylogarithmic operations. So the overall complexity of the exclusion
procedure is $\tilde{\mathcal{O}}(\sqrt{n})$ per point, which is
$\tilde{\mathcal{O}}(\sqrt{n})$ over all the contested points. ∎

With that, the proof of Theorem 20 is completed. Applying the stairs updates
in the proofs of Claims 46 and 55 to $R$ is done implicitly by applying them
to $St_{p}$ while maintaining the extremely periodic invariants after every
update using Lemma 65.

As for the query time, for the close suffixes rank of $S^{i}$ we query
$ActInt$ for $Report([1\ldots i]\times[i\ldots n])$ to obtain the set $P$ of
the intervals containing $i$. The time complexity of this query is
$O(\log^{2}(n)+|P|)=O(\log(n))$. We query every $St_{p}$ such that
$per(p_{1})=p$ for some point $p_{1}\in P$ for $St_{p}[i]$ in $O(\log^{3}(n))$
time each and sum the results to obtain $\Sigma_{p}$. We query $R$ for $R[i]$
in $O(\log(n))$ time and return $R[i]+\Sigma_{p}$. The complexity is dominated
by $O(\log^{4}(n))$.

##  6 Complementary Proofs for Close Suffixes Rank queries

###  6.1 Proof of Lemma 36

See 36

Proof: For $t\in[0\ldots|C|-1]$, let $Ex^{l}_{t}$ and $Ex^{r}_{t}$ be the
extension of the run with period $p$ containing $C$ to the left and to the
right from $w_{t}$, respectively. Since the starting index of $w_{t}$ is
$s_{t}=s_{0}+t\cdot p$, we have $Ex^{l}_{t}=Ex^{C}_{l}+t\cdot p$ and
$Ex^{r}_{t}=Ex^{C}_{r}-t\cdot p$. We proceed to prove the correctness of the
formula for $lcs(s-1,s_{t}-1)$. The formula for $lcp(e+1,e_{t}+1)$ can be
treated similarly.

The run with period $p$ extends at least $m=\min(Ex_{l},Ex^{l}_{t})$ symbols
to the left of both $s$ and $s_{t}$. Let $\delta\in[1\ldots m]$ be an integer.
Let $r_{\delta}\in[0\ldots p-1]$ and $q_{\delta}$ be the two unique integers
such that $\delta=q_{\delta}\cdot p+r_{\delta}$. Due to the extensions of the
run, we have $S[s-\delta]=S[s-r_{\delta}+p]=w[p-r_{\delta}]$. Since the
extension of the period is of size at least $m$ to the left of $s_{t}$ as
well, we have
$S[s_{t}-\delta]=S[s_{t}-r_{\delta}+p]=w_{t}[p-r_{\delta}]=w[p-r_{\delta}]$.
From transitivity, we get $S[s-\delta]=S[s_{t}-\delta]$ for every
$\delta\in[1\ldots m]$ and therefore $lcs(s-1,s_{t}-1)\geq m$.

From our assumption that $Ex_{l}\neq Ex^{C}_{l}+t\cdot p$ we get $Ex_{l}\neq
Ex^{l}_{t}$. If $Ex_{l}<Ex^{l}_{t}$, the extension of the run with period $p$
to the left of $s$ terminates in index $s-(m+1)$. Therefore, $S[s-(m+1)]\neq
S[s-(m+1)+p]$. However, the extensions of the run with period $p$ extends at
least $m+1$ indexes to the left of $s_{t}$. Therefore we have
$S[s_{t}-(m+1)]=S[s_{t}-(m+1)+p]$. We know from $lcs(s-1,s_{t}-1)\geq m$ that
$S[s_{t}+(m+1)-p]=S[s+(m+1)-p]$. From substitution and transitivity we get
$S[s-(m+1)]\neq S[s_{t}-(m+1)]$ and therefore $lcp(s-1,s_{t}-1)=m$. Symmetric
arguments can be made in the case in which $Ex_{l}>Ex^{l}_{t}$.

Evaluating $Ex_{l}$, $Ex_{r}$, $Ex^{C}_{l}$ and $Ex^{C}_{r}$ can be
efficiently executed by querying $LCS(s-1,s+p-1)$, $LCP(e-1,e-p-1)$,
$LCS(s_{0}-1,s_{0}+p-1)$ and $LCP(e_{0}+1,e_{0}-p+1)$ respectively. ∎

###  6.2 Proof of Claim 38

See 38 Proof: We start by proving the following claim:

######  Claim 66.

For every cluster $C=(a,b,p)$ of occurrences, let
$Seq=S^{s_{0}},S^{s_{1}}\ldots S^{s_{|C|-1}}$ be the sequence of suffixes
starting in the starting indexes of occurrences of $W$ implied by $C$. $Seq$
is either an increasing or a decreasing lexicographic sequence.

Proof: Let $s_{i}=a+i\cdot p$ and $s_{i+1}=s_{i}+p$ be two successive starting
indexes of occurrences implied by $C$. Let $Ex_{r}$ be the extension of the
run with period $p$ to the right of $s_{0}$. For every $j\in[s_{0}+p\ldots
s_{0}+Ex_{r}]$ we have $S[j]=S[j-p]$. In particular,
$S[s_{i+1}+x]=S[s_{i}+p+x]=S[s_{i}+x]$ for $x\in[0\ldots Ex_{r}-(i+1)\cdot
p]$. Since the run with period $p$ does not extend to the index
$s_{0}+Ex_{r}+1$, we have
$S[s_{i+1}+Ex_{r}-p\cdot(i+1)+1]=S[s_{0}+Ex_{r}+1]\neq
S[s_{0}+Ex_{r}+1-p]=S[s_{i}+Ex_{r}-(i+1)p+1]$. Therefore,
$lcp(s_{i},s_{i+1})=Ex_{r}-p\cdot(i+1)$ and the lexicographic order between
$s_{i}$ and $s_{i+1}$ is only dependent on the lexicographic order between
$S[s_{0}+Ex_{r}+1]$ and $S[s_{0}+Ex_{r}+1-p]$. The two characters deciding the
order between $s_{i}$ and $s_{i+1}$ are independent from the value of $i$.
Therefore, it is either the case that $S^{s_{i}}<_{L}S^{s_{i+1}}$ for every
$i\in[0\ldots|C|-2]$ or $S^{s_{i}}>_{L}S^{s_{i+1}}$ for every
$i\in[0\ldots|C|-2]$. ∎

Claim 66 guarantees that the values $i\in[0\ldots|C|-1]$ such that
$S^{s}<_{L}S^{s_{i}}$ (resp. $S^{s}>_{L}S^{s_{i}}$) form a consecutive sub
interval $I_{<}$ (resp. $I_{>}$). Specifically either a suffix or a prefix of
$[0\ldots|C|-1]$. We proceed to show how to efficiently evaluate $I_{>}$.
Similar technique can be used to evaluate $I_{<}$.

Let $r_{i}=lcp(s_{i},s)$. for $i\in[0\ldots|C|-1]$. We start by treating the
case in which $r_{0}<|w|$.

Since every $s_{i}$ is a starting index of an occurrence of $w$, we must have
$r_{i}=r_{0}$ for every $i\in[0\ldots|C|-1]$. Therefore, the symbols deciding
the lexicographic order between $S^{s}$ and $S^{s_{i}}$ are $S[s+r_{0}]$ and
$S[s_{i}+r_{0}]$. Since $r_{0}<p$, $S[s_{i}+r_{0}]=w[r_{0}]$. It follows that
the lexicographic order between $S^{s}$ and $S^{s_{i}}$ is independent of $i$,
and therefore either $I_{>}=[1\ldots|C|-1]$ or $I_{>}=\varnothing$. We can
decide which of these two options apply by comparing $S[s+r_{0}]$ and
$w[r_{0}]$.

We proceed to treat the case in which $r_{0}\geq|w|$. If $l_{0}\geq|w|$, we
have that $s$ is a starting index of an occurrence of $w$. Therefore, Lemma 36
can be applied to obtain $r_{i}=\min(Ex_{r},Ex^{C}_{r}-p\cdot i)+|w|$ for
$Ex_{r}\neq Ex^{C}_{r}-p\cdot i$ (with the notations of $Ex_{r}$ and
$Ex^{C}_{r}$ as in the statement of Lemma 36). Let
$i^{\prime}=\frac{Ex_{r}-Ex^{C}_{r}}{p}$. We treat three distinct sub
intervals of $[1\ldots|C|-1]$. For every sub interval. we show that the
lexicographical order between $S^{s}$ and $S^{s_{i}}$ is fixed within the sub
interval.

######  Claim 67.

The interval $[0\ldots i^{\prime})$ is either fully contained in $I_{>}$ or
disjoint from $I_{>}$.

For $i\in[0\ldots i^{\prime})$ we have $Ex_{r}<Ex^{C}_{r}-p\cdot i$ and
therefore $r_{i}=Ex_{r}+|w|$. Therefore, the lexicographical order between
$S^{s}$ and $S^{s_{i}}$ is decided by the values of $S[s+|w|+Ex_{r}]$ and
$S[s_{i}+|w|+Ex_{r}]$. For $i<i^{\prime}$, $s_{i}+|w|+Ex_{r}<s_{0}+p\cdot
i+|w|+Ex^{C}_{r}-p\cdot i=s_{0}+|w|+Ex^{C}_{r}$. Therefore,