Dipartimento di Informatica, University of Verona,
Italyzsuzsanna.liptak@univr.ithttps://orcid.org/0000-0002-3233-0691Partially
funded by the MUR PRIN project Nr. 2022YRB97K ’PINC’ (Pangenome INformatiCs.
From Theory to Applications); member of the GNCS group of the INdAM (Istituto
Nazionale di Alta Matematica “Francesco Severi”). Dipartimento di Informatica,
University of Verona,
Italyfrancesco.masillo@univr.ithttps://orcid.org/0000-0002-2078-6835 Center
for Biotechnology and Bioengineering (CeBiB)
Department of Computer Science, University of Chile,
Chilegnavarro@dcc.uchile.clhttps://orcid.org/0000-0002-2286-741XFunded by
Basal Funds FB0001, Mideplan, Chile, and Fondecyt Grant 1-230755, Chile.
Zsuzsanna Lipták, Francesco Masillo, Gonzalo Navarro[500]Theory of computation
Data structures design and analysis 2024 2024

# A simpler data structure for dynamic strings

Zsuzsanna Lipták  Francesco Masillo  Gonzalo Navarro

###### Abstract

We consider the problem of maintaining a collection of strings while
efficiently supporting splits and concatenations on them, as well as comparing
two substrings, and computing the longest common prefix between two suffixes.
This problem can be solved in optimal time ${\cal O}(\log N)$ whp for the
updates and ${\cal O}(1)$ worst-case time for the queries, where $N$ is the
total collection size [Gawrychowski et al., SODA 2018]. We present here a much
simpler solution based on a forest of enhanced splay trees (FeST), where both
the updates and the substring comparison take ${\cal O}(\log n)$ amortized
time, $n$ being the lengths of the strings involved, and not the total length
$N$ of the strings in the collection. The longest common prefix of length
$\ell$ is computed in ${\cal O}(\log n+\log^{2}\ell)$ amortized time. Our
query results are correct whp. Our simpler solution enables other more general
updates in ${\cal O}(\log n)$ amortized time, such as reversing a substring
and/or mapping its symbols. We can also regard substrings as circular or as
their omega extension.

###### keywords:

dynamic strings, splay trees, dynamic data structures, LCP, circular strings

###### category:

##  1 Introduction

Consider the problem in which we have to maintain a collection of dynamic
strings, that is, strings we want to modify over time. The modifications may
be edit operations such as insertion, deletion, or substitution of a single
character; inserting or deleting an entire substring, possibly creating a new
string from the substring; adding a fresh string to the collection; or even
reversing or complementing a substring. In terms of queries, we may want to
retrieve a symbol or substring of a dynamic string, determine whether two
substrings from anywhere in the collection are equal, or even determine the
longest prefix shared by two suffixes in the collection (LCP). The collection
must be maintained in such a way that both updates and queries have little
cost.

This setup is known in general as the dynamic strings problem. A partial and
fairly straightforward solution are the so-called ropes, or cords [7]. These
are binary trees111The authors [7] actually state that they are DAGs and
referring to them as binary trees is just a simplification. The reason is that
the nodes can have more than one parent, so there are shared subtrees in the
structure. where the leaves store short substrings, whose left-to-right
concatenation forms the string. Ropes were introduced for the Cedar
programming language to speed up handling very long strings; a C
implementation (termed cords) was also given in the same paper [7]. As the
motivating application of ropes/cords was that of implementing a text editor,
they support edit operations and extraction/insertion of substrings to enable
fast typing and cut&paste, plus retrieving substrings, but not more
sophisticated operations like substring equality or LCPs. The trees must be
periodically rebalanced to maintain logarithmic times. Recently, a modified
version of ropes was implemented for the Ruby programming language as basic
data type for strings [30]. This variant supports the same updates but does
not give any theoretical guarantees.

The first solution we know of that enables equality tests, by Sundar and
Tarjan [35], supports splitting and concatenating whole sequences, and whole-
string equality in constant time, with updates taking ${\cal O}(\sqrt{N\log
m}+\log m)$ amortized time, where $N$ is the total length of all the strings
and $m$ is the number of updates so far. It is easy to see that these three
primitives encompass all the operations and queries above, except for LCP
(substring retrieval is often implicit). The update complexity was soon
improved by Mehlhorn et al. [29] to ${\cal O}(\log^{2}N)$ expected time with a
randomized data structure, and ${\cal O}(\log N(\log m\log^{*}m+\log N))$
worst-case time with a deterministic one. The deterministic time complexity
was later improved by Alstrup et al. [1] to ${\cal O}(\log N\log^{*}N)$ with
high probability (whp). Recently, Gawrychowski et al. [19, 20] obtained ${\cal
O}(\log N)$ update time whp, retaining constant time to compare substrings,
and also supported LCP queries in ${\cal O}(1)$ worst-case time (among many
other results). They also showed that the problem is essentially closed
because just updates and substring equality require $\Omega(\log N)$ time even
if allowing amortization.

These results build on the idea of parsing a string hierarchically by
consistently cutting it into blocks, giving unique names to the blocks, and
passing the sequence of names to the next level of parsing. The string is then
represented by a parse tree of logarithmic height, whose root consists of a
single name, which can be compared to the name at the root of another
substring to determine string equality. Gawrychowski et al. [20] mention that

“We note that it is very simple to achieve ${\cal O}(\log n)$ update time […],
if we allow the equality queries to give an incorrect result with polynomially
small probability. We represent every string by a balanced search tree with
characters in the leaves and every node storing a fingerprint of the sequence
represented by its descendant leaves. However, it is not clear how to make the
answers always correct in this approach (even if the time bounds should only
hold in expectation). Furthermore, it seems that both computing the longest
common prefix of two strings of length $n$ and comparing them
lexicographically requires $\Omega(\log^{2}n)$ time in this approach.”

This, of course, connects to the original idea of ropes [7]. While using
binary trees to implement dynamic strings is then not a new idea, we believe
that the possibilities of such an arrangement have not been satisfactorily
explored. In this paper, we show that choosing the right kind of search
tree—an enhanced splay tree—yields a beautifully simple yet powerful data
structure for maintaining dynamic string collections within good theoretical
guarantees and supporting a wide range of operations, several of which have
not been considered before.

#### Our contribution.

We use a splay tree [33], enhanced with additional information, to represent
each string in the collection, where all the nodes contain string symbols (in
in-order), and Karp-Rabin-like fingerprints [26, 31] computed on the nodes. We
refer to our data structure as a forest of enhanced splay trees, or FeST. It
turns out that we can create new strings of length $n$ in ${\cal O}(n)$ worst-
case time, extract substrings of length $\ell$ in ${\cal O}(\log n)$ amortized
plus ${\cal O}(\ell)$ worst-case time, and perform updates and compare
substrings in ${\cal O}(\log n)$ amortized time, where the comparison gives a
correct result whp. Here $n$ is the length of the strings involved, not the
total length $N$ of the strings in the collection. Further, we can compute
LCPs in amortized time ${\cal O}(\log n+\log^{2}\ell)$, where $n$ is the
length of the strings holding the suffixes and $\ell$ is the length of the
returned LCP.

While our LCP time is ${\cal O}(\log^{2}n)$ for long enough $\ell$, LCPs are
usually much shorter than the suffixes. For example, in the very general A2
probabilistic model of Szpankowski [36] to generate strings (which includes
Bernoulli and Markov chains of fixed memory), the maximum LCP value between
any distinct suffixes of two strings of length $n$ is almost surely222A
sequence $X_{n}$ tends to a value $\beta$ almost surely if, for every
$\varepsilon>0$, the probability that $|X_{N}/\beta-1|>\varepsilon$ for some
$N>n$ tends to zero as $n$ tends to infinity,
$\lim_{n\rightarrow\infty}\sup_{N>n}\mathrm{Pr}(|X_{N}/\beta-1|>\varepsilon)=0$.
$\ell={\cal O}(\log n)$, thus our algorithm runs in ${\cal O}(\log n)$
amortized time almost surely under model A2.

The versatility of our FeST data structure allows us to support other kinds of
operations, such as reversing or complementing substrings, or both. We can
thus implement the reverse complementation of a substring in a DNA or RNA
sequence, whereby the substring is reversed and each character is replaced by
its Watson-Crick complement. Substring reversal alone, on the other hand, is
used in classic problems on genome rearrangements where genomes are
represented as sequences of genes, and have to be sorted by reversals (see,
e.g., [38, 6, 10, 11, 32, 12], to cite just some from the rich literature).
Note that chromosomes can be viewed either as permutations or as strings, when
gene duplication is taken into account, see Fertin et al. [17]; our FeST data
structure accommodates both. We can also implement signed reversals [24, 23],
another model of evolutionary operation used in genome rearrangements. In
general, we can combine reversals with any involution on the alphabet, of
which signed or Watson-Crick complementation are only examples. In order to
support these operations in ${\cal O}(\log n)$ amortized time, we only need to
add new constant-space annotations, further enhancing our splay trees while
retaining the running times for the other operations. Full details on
involutions can be found in the appendix.

Concretely, we maintain a collection of strings of total length $N$ in ${\cal
O}(N)$ space, and support the following operations333Note that we have not
chose a minimal set of primitives because we prefer this richer interface for
the sake of an easier exposition., where we distinguish the basic string data
type from dynamic strings:

  * •

$\texttt{make-string}(w)$ creates, from a basic string $w$, a dynamic string
$s$ with the same content, in ${\cal O}(|s|)$ worst-case time (the growth of
the potential function is also bounded by ${\cal O}(|s|)$).

  * •

$\texttt{access}(s,i)$ returns the symbol $s[i]$ in ${\cal O}(\log|s|)$
amortized time.

  * •

$\texttt{retrieve}(s,i,j)$ returns the basic string $w[1..j-i+1]=s[i..j]$, in
${\cal O}(\log|s|)$ amortized plus ${\cal O}(|w|)$ worst-case time.

  * •

$\texttt{substitute}(s,i,c)$, $\texttt{insert}(s,i,c)$, and
$\texttt{delete}(s,i)$ perform the basic edit operations on $s$: substituting
$s[i]$ by character $c$, inserting $c$ at $s[i]$, and deleting $s[i]$,
respectively, all in ${\cal O}(\log|s|)$ amortized time. For appending $c$ at
the end of $s$ one can use $\texttt{insert}(s,|s|+1,c)$.

  * •

$\texttt{introduce}(s_{1},i,s_{2})$ inserts $s_{2}$ at position $i$ of $s_{1}$
(for $1\leq i\leq|s_{1}|+1$), converting $s_{1}$ to $s_{1}[..i-1]\cdot
s_{2}\cdot s_{1}[i..]$ and destroying $s_{2}$, in ${\cal O}(\log|s_{1}s_{2}|)$
amortized time.

  * •

$\texttt{extract}(s,i,j)$ extracts a new dynamic string $s^{\prime}=s[i..j]$,
removing it from $s$, in ${\cal O}(\log|s|)$ amortized time.

  * •

$\texttt{equal}(s_{1},i_{1},s_{2},i_{2},\ell)$ determines the equality of
substrings $s_{1}[i_{1}..i_{1}+\ell-1]$ and $s_{2}[i_{2}..i_{2}+\ell-1]$ in
${\cal O}(\log|s_{1}s_{2}|)$ amortized time, correctly whp.

  * •

$\texttt{lcp}(s_{1},i_{1},s_{2},i_{2})$ computes the length $\ell$ of the
longest common prefix between suffixes $s_{1}[i_{1}..]$ and $s_{2}[i_{2}..]$,
in ${\cal O}(\log|s_{1}s_{2}|+\log^{2}\ell)$ amortized time, correctly whp,
and also tells which suffix is lexicographically smaller.

  * •

$\texttt{reverse}(s,i,j)$ reverses the substring $s[i..j]$ of $s$, in ${\cal
O}(\log|s|)$ amortized time.

  * •

$\texttt{map}(s,i,j)$ applies a fixed involution (a symbol mapping that is its
own inverse) to all the symbols of $s[i..j]$, in ${\cal O}(\log|s|)$ amortized
time.

Our data structure also offers other features that previous solutions lack,
such as handling circular strings. This is an important and emerging topic [5,
14, 21, 22, 25], as many current sequence collections, in particular in
computational biology, consist of circular rather than linear strings. Recent
data structures built for circular strings [8, 9], based on the extended
Burrows-Wheeler Transform [28], avoid the detour via the linearization and
handle the circular input strings directly. Finally, FeST also allows queries
on the omega extensions of strings, i.e. on the infinite concatentation
$s^{\omega}=s\cdot s\cdot s\cdots$. This can be used, for example, when
computing the so-called omega-order, the order underlying the extended BWT of
[28]. FeST also allows to ensure string uniqueness, should this feature be
required. For full details on these features, see the Appendix.

#### Related models.

A related line of work aims at maintaining a data structure such that the
solution to some particular problem on one or two strings can be efficiently
updated when these strings undergo an edit operation (deletion, insertion, or
substitution). Examples are longest common factor of two strings [3, 4],
optimal alignment of two strings [13], longest palindromic substring [18],
longest square [2], or longest Lyndon factor [37] of one string. The setup can
be what is referred to as partially dynamic, when the original string or
strings are returned to their state before the edit, or fully dynamic, when
the edit operations are reflected on the original string or strings. Clifford
et al. [15] give lower bounds on various problems of this kind when a single
substitution is applied.

This setup, also referred to as dynamic strings, differs from ours in several
ways: (a) we are not only interested in solving one specific problem on
strings; (b) we have an entire collection of strings, and will want to ask
queries on any one or any pair of these; and (c) we allow many different kinds
of update operations.

##  2 Basic concepts

#### Strings.

We use array-based notation for strings, indexing from 1, so a string $s$ is a
finite sequence over a finite ordered alphabet $\Sigma$, written
$s=s[1]s[2]\cdots s[n]$, for some $n\geq 0$. The length of $s$ is denoted
$|s|$, and $\varepsilon$ denotes the empty string, the unique string of length
$0$. For $1\leq i,j\leq|s|$, we write $s[i..j]=s[i]s[i+1]\cdots s[j]$ for the
substring from $i$ to $j$, where $s[i..j]=\varepsilon$ if $i>j$. We write
prefixes as $s[..i]=s[1..i]$ and suffixes as $s[i..]=s[i..|s|]$. Given two
strings $s,t$, their concatenation is written as $s\cdot t$ or simply $st$,
and $s^{k}$ denotes the $k$-fold concatenation of $s$, with
$s^{0}=\varepsilon$. A substring (prefix, suffix) of $s$ is called proper if
it does not equal $s$. A string $s$ is called periodic with period $r$ if
$s[i+r]=s[i]$ for all $1\leq i\leq|s|-r$.

The longest common prefix (LCP) of two strings $s$ and $t$ is defined as the
longest prefix $u$ that is both a prefix of $s$ and $t$, and
$\mathrm{lcp}(s,t)=|u|$ as its length. One can define the lexicographic order
based on the lcp: $s<_{{\textrm{lex}}}t$ if either $s$ is a proper prefix of
$t$, or otherwise if $s[\ell+1]<t[\ell+1],$ where $\ell=\mathrm{lcp}(s,t)$.

#### Splay trees.

The splay tree [33] is a binary search tree that guarantees that a sequence of
insertions, deletions, and node accesses costs ${\cal O}(\log n)$ amortized
time per operation on a tree of $n$ nodes that starts initially empty. In
addition, splay trees support splitting and joining trees, both in ${\cal
O}(\log n)$ amortized time, where $n$ is the total number of nodes involved in
the operation.

The basic operation of the splay tree is called $\textit{splay}(x)$, which
moves a tree node $x$ to the root by a sequence of primitive rotations called
zig, zig-zig, zig-zag, and their symmetric versions. Let $x(A,B)$ denote a
tree rooted at $x$ with left and right subtrees $A$ and $B$, then the rotation
zig-zig converts $z(y(x(A,B),C),D)$ into $x(A,y(B,z(C,D))$, while the rotation
zig-zag converts $z(y(A,x(B,C)),D)$ into $x(y(A,B),z(C,D))$. Whether zig-zig
or zig-zag (or their symmetric variant) is applied to $x$ depends on its
relative position w.r.t. its grandparent in the tree. Note that both of these
operations are compositions of two edge rotations. Finally, operation zig,
which is only applied if $x$ is a child of the root, converts $y(x(A,B),C)$
into $x(A,y(B,C))$.

Every access or update on the tree is followed by a splay on the affected
node, or a related one. In particular, after finding a node $x$ in a downward
traversal, we do $\textit{splay}(x)$ to make $x$ the tree root. The goal is
that the costs of all the operations are proportional to the cost of all the
related splay operations performed, so we can focus on analyzing only the
splays. Many of the splay tree properties can be derived from a general
“access lemma” [33, Lem. 1].

######  Lemma 2.1 (Access Lemma [33]).

Let us assign any positive weight $w(x)$ to the nodes $x$ of a splay tree $T$,
and define $sw(x)$ as the sum of the weights of all the nodes in the subtree
rooted at $x$. Then, the amortized time to splay $x$ is ${\cal
O}(\log(W/sw(x)))\subseteq{\cal O}(\log(W/w(x)))$, where $W=\sum_{x\in
T}w(x)$.

The result is obtained by defining $r(x)=\log sw(x)$ (all our logarithms are
in base 2) and $\Phi(T)=\sum_{x\in T}r(x)$ as the potential function for the
splay tree $T$. For example, if we choose $w(x)=1$ for all $x$, then $W=n$ on
a splay tree of $n$ nodes, and thus we obtain ${\cal O}(\log n)$ amortized
cost for each operation. By choosing other functions $w(x)$, one can prove
other properties of splay trees like static optimality, the static finger
property, and the working set property [33].

The update operations supported by splay trees include inserting new nodes,
deleting nodes, joining two trees (where all the nodes in the second tree go
to the right of the nodes in the first tree), and splitting a tree into two at
some node (where all the nodes to its right become a second tree). The times
of those operations are ruled by the “balance theorem with updates” [33, Thm.
6].

######  Lemma 2.2 (Balance Theorem with Updates [33]).

Any sequence of access, insert, delete, join and split operations on a
collection of initially empty splay trees has an amortized cost of ${\cal
O}(\log n)$ per operation, where $n$ is the size of the tree where each
operation is carried out.

This theorem is proved with the potential function that assigns $w(x)=1$ to
every node $x$. Note the theorem considers a forest of splay trees, whose
potential function is the sum of the functions $\Phi(T)$ over the trees $T$ in
the forest.

#### Karp-Rabin fingerprinting.

Our queries will be correct “with high probability” (whp), meaning a
probability of at least $1-1/N^{c}$ for an arbitrarily large constant $c$,
where $N$ is the total size of the collection. This will come from the use of
a variant of the original Karp-Rabin fingerprint [26] (cf. [31]) defined as
follows. Let $[1..a]$ be the alphabet of our strings and $p\geq a$ a prime
number. We choose a random base $b$ uniformly from $[1..p-1]$. The fingerprint
$\kappa$ of string $s[1..n]$ is defined as
$\kappa(s)=\left(\sum_{i=0}^{n-1}s[n-i]\cdot b^{i}\right)\bmod p$. We say that
two strings $s\neq s^{\prime}$ of the same length $n$ collide through $\kappa$
if $\kappa(s)=\kappa(s^{\prime})$, that is, $\kappa(s-s^{\prime})=0$, where
$s^{\prime\prime}=s-s^{\prime}$ is the string defined by
$s^{\prime\prime}[i]=(s[i]-s^{\prime}[i])\bmod p$. Since
$\kappa(s^{\prime\prime})$ is a polynomial, in the variable $b$, of degree at
most $n-1$ in the field $\mathbb{Z}_{p}$, it has at most $n-1$ roots. The
probability of a collision between two strings of length $n$ is then bounded
by $(n-1)/(p-1)$ because $b$ is uniformly chosen in $[1..p-1]$. By choosing
$p\in\Theta(N^{c+1})$ for any desired constant $c$, we obtain that $\kappa$ is
collision-free between $s$ and $s^{\prime}$ whp. We will actually choose
$p\in\Theta(N^{c+2})$ because some of our operations perform ${\cal
O}(\mathrm{polylog}\,N)$ string comparisons, not just one. Since $N$ varies
over time, we can use instead a fixed upper bound, like the total amount of
main memory. We use the RAM machine model where logical and arithmetic
operations on $\Theta(\log N)$ machine words take constant time.

Two fingerprints $\kappa(s)$ and $\kappa(s^{\prime})$ can be composed in
constant time to form $\kappa(s^{\prime}\cdot s)=(\kappa(s^{\prime})\cdot
b^{|s|}+\kappa(s))\bmod p$. To this end we will also maintain, together with
$\kappa(s)$, the value $b^{|s|}\bmod p$, to avoid the ${\cal O}(\log|s|)$ time
to compute it with modular exponentiation. The corresponding value for
$s^{\prime}\cdot s$ is $(b^{|s^{\prime}|}\cdot b^{|s|})\bmod p$, so we can
maintain those powers in constant time upon string concatenations.

##  3 Our data structure and standard operations

In this section we describe our data structure called FeST (for Forest of
enhanced Splay Trees), composed of a collection of (enhanced) splay trees, and
then show how the traditional operations on dynamic strings are carried out on
it.

###  3.1 The data structure

We will use a FeST for maintaining the collection of strings, one splay tree
per string. A dynamic string $s[1..n]$ is encoded in a splay tree with $n$
nodes such that $s[k]$ is stored in the node $x$ with in-order $k$. We will
say that node $x$ represents the substring $s[i..j]$, where $[i..j]$ is the
range of the in-orders of all the nodes in the subtree rooted at $x$. Let $T$
be the splay tree representing string $s$, then for $1\leq i\leq|s|$, we call
$\textit{node}(i)$ the node with in-order $i$, and for a node $x$ of $T$, we
call $\textit{pos}(x)$ the in-order of node $x$. The root of $T$ is denoted
$\textit{root}(T)$.

For the amortized analysis of our FeST, our potential function $\Phi$ will be
the sum of the potential functions $\Phi(T)$ over all the splay trees $T$
representing our string collection. The collection starts initially empty,
with $\Phi=0$. New strings are added to the collection with make-string; then
edited with substitute, insert, and delete, and redistribute with introduce
and extract.

#### Information stored at nodes.

A node $x$ of the splay tree representing $s[i..j]$ will contain the
information of its left and right child, called $x.\mathrm{left}$ and
$x.\mathrm{right}$, its symbol $x.\mathrm{char}=s[\textit{pos}(x)]$, its
subtree size $x.\mathrm{size}=j-i+1$, its fingerprint
$x.\mathrm{fp}=\kappa(s[i..j])$, and the value
$x.\mathrm{power}=b^{j-i+1}\bmod p$. These fields are recomputed in constant
time whenever a node $x$ acquires new children $x.\mathrm{left}$ and/or
$x.\mathrm{right}$ (e.g., during the splay rotations) with the following
formulas: (1)
$x.\mathrm{size}=x.\mathrm{left}.\mathrm{size}+1+x.\mathrm{right}.\mathrm{size}$,
(2) $x.\mathrm{fp}=((x.\mathrm{left}.\mathrm{fp}\cdot b+x.\mathrm{char})\cdot
x.\mathrm{right}.\mathrm{power}+x.\mathrm{right}.\mathrm{fp})\bmod p$, and (3)
$x.\mathrm{power}=(x.\mathrm{left}.\mathrm{power}\cdot b\cdot
x.\mathrm{right}.\mathrm{power})\bmod p$, as explained in Section 2. For the
formula to be complete when the left and/or right child is null, we assume
$null.\mathrm{size}=0$, $null.\mathrm{fp}=0$, and $null.\mathrm{power}=1$. We
will later incorporate other fields to support string reversals and mappings.

Subtree sizes allow us identify $\textit{node}(i)$ given $i$, in the splay
tree $T$ representing string $s$, in ${\cal O}(\log|s|)$ amortized time. This
means we can answer $\texttt{access}(s,i)$ in ${\cal O}(\log|s|)$ amortized
time, since $s[i]=\textit{node}(i).\mathrm{char}$. Finding $\textit{node}(i)$
is done in the usual way, with the recursive function $\texttt{find}(i)=$
$\texttt{find}(\textit{root}(T),i)$ that returns the $i$th smallest element in
the subtree rooted at the given node. More precisely, $\texttt{find}(x,i)=x$
if $i=x.\mathrm{left}.\mathrm{size}+1$,
$\texttt{find}(x,i)=\texttt{find}(x.\mathrm{left},i)$ if
$i<x.\mathrm{left}.\mathrm{size}+1$, and
$\texttt{find}(x,i)=\texttt{find}(x.\mathrm{right},i-(x.\mathrm{left}.\mathrm{size}+1))$
if $i>x.\mathrm{left}.\mathrm{size}+1$. To obtain logarithmic amortized time,
find splays the node it returns, thus $\textit{pos}(\textit{root}(T))=i$ holds
after calling $\texttt{find}(\textit{root}(T),i)$.

#### Isolating substrings.

We will make extensive use of another primitive we call
$\texttt{isolate}(i,j)$, for $1\leq i,j\leq|s|$ and $i\leq j+1$, on a tree $T$
representing string $s$. This operation rearranges $T$ in such a way that
$s[i..j]$ becomes represented by one subtree, and returns this subtree’s root
$y$.

If $i=1$ and $j=n$, then $y=\textit{root}(T)$ and we are done. If $i=1$ and
$j<n$, then we find (and splay) $\textit{node}(j+1)$ using
$\texttt{find}(j+1)$; this will move $\textit{node}(j+1)$ to the root, and
$s[i..j]$ will be represented by the left subtree of the root, so
$y=\textit{root}(T).\mathrm{left}$. Similarly, if $1<i$ and $j=n$, then we
perform $\texttt{find}(i-1)$, so $\textit{node}(i-1)$ is splayed to the root
and $s[i..j]$ is represented by the right subtree of the root, thus
$y=\textit{root}(T).\mathrm{right}$.

Finally, if $1<i,j<n$, then splaying first $\textit{node}(j+1)$ and then
$\textit{node}(i-1)$ will typically result in $\textit{node}(i-1)$ being the
root and $\textit{node}(j+1)$ its right child, thus the left subtree of
$\textit{node}(j+1)$ contains $s[i..j]$, that is,
$y=\textit{root}(T).\mathrm{right}.\mathrm{left}$. The only exception arises
if the last splay operation on $\textit{node}(i-1)$ is a zig-zig, as in this
case $\textit{node}(j+1)$ would become a grandchild, not a child, of the root.
Therefore, in this case, we modify the last splay operation: if
$\textit{node}(i-1)$ is a grandchild of the root and a zig-zig must be
applied, we perform instead two consecutive zig operations on
$\textit{node}(i-1)$ in a bottom-up manner, that is, we first rotate the edge
between $\textit{node}(i-1)$ and its parent, and then the edge between
$\textit{node}(i-1)$ and its new parent (former grandparent).

We now consider the effect of the modified zig-zig operation on the potential.
In the proof of Lemma 2.1 [33, Lem. 1], Sleator and Tarjan show that the zig-
zig and the zig-zag cases contribute $3(r^{\prime}(x)-r(x))$ to the amortized
cost, where $r^{\prime}(x)$ is the new value of $r(x)$ after the operation.
The sum then telescopes to $3(r(t)-r(x))=3\log(sw(t)/sw(x))$ along an upward
path towards a root node $t$. The zig rotation, instead, contributes
$1+r^{\prime}(x)-r(x)$, where the $1$ would be problematic if it was not
applied only once in the path. Our new zig-zig may, at most one time in the
path, cost like two zig’s, $2+2(r^{\prime}(x)-r(x))$, which raises the cost
bound of the whole splay operation from $1+3\log(sw(t)/sw(x))$ to
$2+3\log(sw(t)/sw(x))$. This does not alter the amortized complexity, that is,
the amortized time for $\texttt{isolate}(i,j)$ is ${\cal O}(\log|s|)$.

###  3.2 Creating a new dynamic string

Given a basic string $w[1..n]$, operation $\texttt{make-string}(w)$ creates a
new dynamic string $s[1..n]$ with the same content as $w$, which is added to
the FeST. While this can be accomplished in ${\cal O}(n\log n)$ amortized time
via successive insert operations on an initially empty string, we describe
here a “bulk-loading” technique that achieves linear worst-case (and
amortized) time.

The idea is to create, in ${\cal O}(n)$ time, a perfectly balanced splay tree
using the standard recursive procedure. As we show in the next lemma, this
shape of the tree adds only ${\cal O}(n)$ to the potential function, and
therefore the amortized time of this procedure is also ${\cal O}(n)$.

######  Lemma 3.1.

The potential $\Phi(T)$ of a perfectly balanced splay tree $T$ with $n$ nodes
is at most $2n+{\cal O}(\log^{2}n)\subseteq{\cal O}(n)$.

######  Proof 3.2.

Let $d$ be the depth of the deepest leaves in a perfectly balanced binary
tree, and call $l=d-d^{\prime}+1$ the level of any node of depth $d^{\prime}$.
It is easy to see that there are at most $1+n/2^{l}$ subtrees of level $l$.
Those subtrees have at most $2^{l}-1$ nodes. Separating the sum
$\Phi(T)=\sum_{x\in T}r(x)$ by levels $l$ and using the bound $sw(x)<2^{l}$ if
$x$ is of level $l$, we get $\Phi(T)<\sum_{l=1}^{\log
n}\left(1+\frac{n}{2^{l}}\right)\log 2^{l}=2n+{\cal O}(\log^{2}n).$

Once the tree is created and the fields $x.\mathrm{char}$ are assigned in in-
order, we perform a post-order traversal to compute the other fields. This is
done in constant time per node using the formulas given in Section 3.1.

###  3.3 Retrieving a substring

Given a string $s$ in the FeST and two indices $1\leq i\leq j\leq|s|$,
operation $\texttt{retrieve}(s,i,j)$ extracts the substring $s[i..j]$ and
returns it as a basic string. The special case $i=j$ is given by
$\texttt{access}(s,i)$, which finds $\textit{node}(i)$, splays it, and returns
$\textit{root}(T).\mathrm{char}$, recall Section 3.1. If $i<j$, we perform
$y=\texttt{isolate}(i,j)$ and then we return $s[i..j]$ with an in-order
traversal of the subtree rooted at $y$. Overall, the operation
$\texttt{retrieve}(s,i,j)$ takes ${\cal O}(\log|s|)$ amortized time for
isolate, and then ${\cal O}(j-i+1)$ worst case time for the traversal of the
subtree.

###  3.4 Edit operations

Let $s$ be a string in the FeST, $i$ an index of $s$, and $c$ a character. The
simplest edit operation, $\texttt{substitute}(s,i,c)$ writes $c$ at $s[i]$,
that is, $s$ becomes $s^{\prime}=s[..i-1]\cdot c\cdot s[i+1..]$. It is
implemented by doing $\texttt{find}(i)$ in the splay tree $T$ of $s$, in
${\cal O}(\log|s|)$ amortized time. After the operation, $\textit{node}(i)$ is
the root, so we set $\textit{root}(T).\mathrm{char}=c$ and recompute (only)
its fingerprint as explained in Section 3.1.

Now consider operation $\texttt{insert}(s,i,c)$, which converts $s$ into
$s^{\prime}=s[..i-1]\cdot c\cdot s[i..]$. This corresponds to the standard
insertion of a node in the splay tree, at in-order position $i$. We first use
$\texttt{find}(i)$ in order to make $x=\textit{node}(i)$ the tree root, and
then create a new root node $y$, with $y.\mathrm{left}=x.\mathrm{left}$ and
$y.\mathrm{right}=x$. We then set $x.\mathrm{left}=null$ and recompute the
other fields of $x$ as shown in Section 3.1. Finally, we set
$y.\mathrm{char}=c$ and also compute its other fields. By Lemma 2.2, the
amortized cost for an insertion is ${\cal O}(\log|s|)$.

Finally, the operation $\texttt{delete}(s,i)$ converts $s$ into
$s^{\prime}=s[..i-1]\cdot s[i+1..]$. This corresponds to the standard deletion
in the splay tree: we first do $\texttt{find}(i)$ in the tree $T$ of $s$, so
that $x=\textit{node}(i)$ becomes the root, and then we join the splay trees
of $x.\mathrm{left}$ and $x.\mathrm{right}$, isolating the root node $x$ and
freeing it. The joined tree now represents $s^{\prime}$; the amortized cost is
${\cal O}(\log|s|)$.

###  3.5 Introducing and extracting substrings

Given two strings $s_{1}$ and $s_{2}$ represented by trees $T_{1}$ and $T_{2}$
in the FeST, and an insertion position $i$ in $s_{1}$, operation
$\texttt{introduce}(s_{1},i,s_{2})$ generates a new string
$s=s_{1}[..i-1]\cdot s_{2}\cdot s_{1}[i..]$ (the original strings are not
anymore available). We implement this operation by first doing
$y=\texttt{isolate}(i,i-1)$ on the tree $T_{1}$. Note that in this case $y$
will be a $null$ node, whose in-order position is between $i-1$ and $i$. We
then replace this null node by (the root of) the tree $T_{2}$. As shown in
Section 3.1, the node $y$ that we replace has at most two ancestors in
$T_{1}$, say $x_{1}$ (the root) and $x_{2}$. We must then recompute the fields
of $x_{2}$ and then of $x_{1}$.

Apart from the ${\cal O}(\log|s_{1}|)$ amortized time for isolate, the other
operations take constant time. We must consider the change in the potential
introduced by connecting $T_{2}$ to $T_{1}$. In the potential $\Phi$, the
summands $\log sw(x_{1})$ and $\log sw(x_{2})$ will increase to
$\log(sw(x_{1})+|s_{2}|)$ and $\log(sw(x_{2})+|s_{2}|)$, thus the increase is
${\cal O}(\log|s_{2}|)$. The total amortized time is thus ${\cal
O}(\log|s_{1}|+\log|s_{2}|)={\cal O}(\log|s_{1}s_{2}|)$.

Let $s$ be a string represented by tree $T$ in the FeST and $i\leq j$ indices
in $s$. Function $\texttt{extract}(s,i,j)$ removes $s[i..j]$ from $s$ and
creates a new dynamic string $s^{\prime}$ from it. This can be carried out by
first doing $y=\texttt{isolate}(i,j)$ on $T$, then detaching $y$ from its
parent in $T$ to make it the root of the tree that will represent
$s^{\prime}$, and finally recomputing the fields of the (former) ancestors
$x_{2}$ and $x_{1}$ of $y$. The change in potential is negative, as $\log
sw(x_{1})$ and $\log sw(x_{2})$ decrease by up to ${\cal O}(\log(j-i+1))$. The
total amortized time is then ${\cal O}(\log|s|)$.

###  3.6 Substring equality

Let $s_{1}[i_{1}..i_{1}+\ell-1]$ and $s_{2}[i_{2}..i_{2}+\ell-1]$ be two
substrings, where possibly $s_{1}=s_{2}$. Per Section 2, we can compute equal
whp by comparing $\kappa(s_{1}[i_{1}..i_{1}+\ell-1])$ and
$\kappa(s_{2}[i_{2}..i_{2}+\ell-1])$. To obtain those values, we compute
$y_{1}=\texttt{isolate}(i_{1},i_{1}+\ell-1)$ on the tree of $s_{1}$ and
$y_{2}=\texttt{isolate}(i_{2},i_{2}+\ell-1)$ on the tree of $s_{2}$. Once node
$y_{1}$ represents $s_{1}[i_{1}..i_{1}+\ell-1]$ and $y_{2}$ represents
$s_{2}[i_{2}..i_{2}+\ell-1]$, we compare
$y_{1}.\mathrm{fp}=\kappa(s_{1}[i_{1}..i_{1}+\ell-1])$ with
$y_{2}.\mathrm{fp}=\kappa(s_{2}[i_{2}..i_{2}+\ell-1])$.

The splay operations take ${\cal O}(\log|s_{1}s_{2}|)$ amortized time, while
the comparison of the fingerprints takes constant time and returns the correct
answer whp. Note this is a one-sided error; if the method answers negatively,
the strings are distinct.

##  4 Extended operations

In this section we consider less standard operations of dynamic strings,
including the computation of LCPs (considered only recently [20]) and others
we have not seen addressed before.

###  4.1 Longest common prefixes

Operation $\texttt{lcp}(s_{1},i_{1},s_{2},i_{2})$ computes
$\mathrm{lcp}(s_{1}[i_{1}..],s_{2}[i_{2}..])$ correctly whp, by exponentially
searching for the maximum value $\ell$ such that
$s_{1}[i_{1}..i_{1}+\ell-1]=s_{2}[i_{2}..i_{2}+\ell-1]$. The exponential
search requires ${\cal O}(\log\ell)$ equality tests, which are done using
equal operations. The amortized cost of this basic implementation is then
${\cal O}(\log|s_{1}s_{2}|\log\ell)$; we now seek to improve it.

We note that all the accesses the exponential search performs in $s_{1}$ and
$s_{2}$ are at distance ${\cal O}(\ell)$ from $s_{1}[i_{1}]$ and
$s_{2}[i_{2}]$. We could then use the dynamic finger property [16] to show,
with some care, that the amortized time is ${\cal
O}(\log|s_{1}s_{2}|+\log^{2}\ell)$. This property, however, uses a different
mechanism of potential functions where trees cannot be joined or split.444The
static finger property cannot be used either, because we need new fingers
every time an LCP is computed. Extending the “unified theorem” [33, Thm. 5] to
having $m$ fingers (so as to support $m$ LCP operations in the sequence)
introduces an ${\cal O}(\log m)$ additive amortized time in the operations,
since now $W=\Theta(m)$. We then use an alternative approach. The main idea is
that, if we could bound $\ell$ beforehand, we could isolate those areas so
that the accesses inside them would cost ${\cal O}(\log\ell)$ and then we
could reach the desired amortized time. Bounding $\ell$ in less than ${\cal
O}(\log\ell)$ accesses (i.e., ${\cal O}(\log|s_{1}s_{2}|\log\ell)$ time) is
challenging, however. Assuming for now that $s_{1}\not=s_{2}$ (we later handle
the case $s_{1}=s_{2}$), our plan is as follows:

  1. 1.

Find a (crude) upper bound $\ell^{\prime}\geq\ell$.

  2. 2.

Extract substrings $s_{1}^{\prime}=s_{1}[i_{1}..i_{1}+\ell^{\prime}-1]$ and
$s_{2}^{\prime}=s_{2}[i_{2}..s_{2}+\ell^{\prime}-1]$.

  3. 3.

Run the basic exponential search for $\ell$ between $s_{1}^{\prime}[1..]$ and
$s_{2}^{\prime}[1..]$.

  4. 4.

Reinsert substrings $s_{1}^{\prime}$ and $s_{2}^{\prime}$ into $s_{1}$ and
$s_{2}$.

Steps 2 and 4 are carried out in ${\cal O}(\log|s_{1}s_{2}|)$ amortized time
using the operations extract and introduce, respectively. Step 3 will still
require ${\cal O}(\log\ell)$ substring comparisons, but since they will be
carried out on the shorter substrings $s_{1}^{\prime}$ and $s_{2}^{\prime}$,
they will take ${\cal O}(\log\ell\log\ell^{\prime})$ amortized time. The main
challenge is to balance the cost to find $\ell^{\prime}$ in Step 1 with the
quality of the approximation of $\ell^{\prime}$ so that $\log\ell^{\prime}$ is
not much larger than $\log\ell$.

Consider the following strategy for Step 1. Let $n=|s_{1}s_{2}|$ and
$n^{\prime}=\min(|s_{1}|-i_{1}+1,|s_{2}|-i_{2}+1)$. We first check a few
border cases that we handle in ${\cal O}(\log n)$ amortized time: if
$s_{1}[i_{1}..i_{1}+n^{\prime}-1]=s_{2}[i_{2}..i_{2}+n^{\prime}-1]$ we finish
with the answer $\ell=n^{\prime}$, or else if
$s_{1}[i_{1}..i_{1}+1]\not=s_{2}[i_{2}..i_{2}+1]$ we finish with the answer
$\ell=0$ or $\ell=1$. Otherwise, we define the sequence $\ell_{0}=2$ and
$\ell_{i}=\min(n^{\prime},\ell_{i-1}^{\,2})$ and try out the values $\ell_{i}$
for $i=1,2,\ldots$, until we obtain
$s_{1}[i_{1}..i_{1}+\ell_{i}-1]\not=s_{2}[i_{2}..i_{2}+\ell_{i}-1]$. This
implies that $\ell_{i-1}\leq\ell<\ell_{i}$, so we can use
$\ell^{\prime}=\ell_{i}\leq\ell^{2}$. This yields ${\cal
O}(\log\ell\log\ell^{\prime})={\cal O}(\log^{2}\ell)$ amortized time for Step
3. On the other hand, since $\ell\geq\ell_{i-1}=2^{2^{i-1}}$, it holds $i\leq
1+\log\log\ell$. Since each of the $i$ values is tried out in ${\cal O}(\log
n)$ time with equal, the amortized cost of Step 1 is ${\cal O}(\log
n\log\log\ell)$ and the total cost to compute lcp is ${\cal O}(\log
n\log\log\ell+\log^{2}\ell)$. In particular, this is ${\cal O}(\log^{2}\ell)$
when $\ell$ is large enough, $\log\ell=\Omega(\sqrt{\log n\log\log n})$.

#### Hitting twice.

To obtain our desired time ${\cal O}(\log n+\log^{2}\ell)$ for every value of
$\log\ell$, we will apply our general strategy twice. First, we will set
$\ell^{\prime\prime}=2^{\log^{2/3}n}$ and determine whether
$s_{1}[i_{1}..i_{1}+\ell^{\prime\prime}-1]=s_{2}[i_{2}..i_{2}+\ell^{\prime\prime}-1]$.
If they are equal, then $\log\ell=\Omega(\log^{2/3}n)$ and we can apply the
strategy of the previous paragraph verbatim, obtaining amortized time ${\cal
O}(\log^{2}\ell)$. If they are not equal, then we know that
$\ell^{\prime\prime}>\ell$, so we extract
$s_{1}^{\prime\prime}=s_{1}[i_{1}..i_{1}+\ell^{\prime\prime}-1]$ and
$s_{2}^{\prime\prime}=s_{2}[i_{2}..i_{2}+\ell^{\prime\prime}-1]$ to complete
the search for $\ell^{\prime}$ inside those (note we are still in Step 1). We
use the same sequence $\ell_{i}$ of the previous paragraph, with the only
difference that the accesses are done on trees of size $\ell^{\prime\prime}$
and not $n$; therefore each step costs ${\cal
O}(\log\ell^{\prime\prime})={\cal O}(\log^{2/3}n)$ instead of ${\cal O}(\log
n)$. After finally finding $\ell^{\prime}$, we introduce back
$s_{1}^{\prime\prime}$ and $s_{2}^{\prime\prime}$ into $s_{1}$ and $s_{2}$.
Step 1 then completes in amortized time ${\cal O}(\log
n+\log^{2/3}n\log\log\ell)={\cal O}(\log n)$. Having found
$\ell^{\prime}\leq\ell^{2}$, we proceed with Step 2 onwards as above, taking
${\cal O}(\log^{2}\ell)$ additional time.

#### When the strings are the same.

In the case $s_{1}=s_{2}$, assume w.l.o.g. $i_{1}<i_{2}$. We can still carry
out Step 1 and, if $i_{1}+\ell^{\prime}\leq i_{2}$, proceed with the plan in
the same way, extracting $s_{1}^{\prime}$ and $s_{2}^{\prime}$ from the same
string and later reintroducing them. In case $i_{1}+\ell^{\prime}>i_{2}$,
however, both substrings overlap. In this case we extract just one substring,
$s^{\prime}=s_{1}[i_{1}..i_{2}+\ell^{\prime}-1]$, which is of length at most
$2\ell^{\prime}$, and run the basic exponential search between
$s^{\prime}[1..]$ and $s^{\prime}[i_{2}-i_{1}+1..]$ still in amortized time
${\cal O}(\log\ell\log\ell^{\prime})$. We finally reintroduce $s^{\prime}$ in
$s_{1}$. The same is done if we need to extract $s_{1}^{\prime\prime}$ and
$s_{2}^{\prime\prime}$: if both come from the same string and
$i_{1}+\ell^{\prime\prime}>i_{2}$, then we extract just one single string
$s^{\prime\prime}=s[i_{1}..i_{2}+\ell^{\prime\prime}-1]$ and obtain the same
asymptotic times.

#### Lexicographic comparison.

Once we know that the LCP of the suffixes is of length $\ell$, we can
determine which is lexicographically smaller by accessing (using operation
access) the symbols at positions $s_{1}[i_{1}+\ell]$ and $s_{2}[i_{2}+\ell]$
and comparing them, in ${\cal O}(\log|s_{1}s_{2}|)$ additional amortized time.

###  4.2 Substring reversals

Operation $\texttt{reverse}(s,i,j)$ changes $s$ to $s[..i-1]s[j]s[j-1]\cdots
s[i+1]s[i]s[j+1..]$. Reflecting it directly in our current structure requires
$\Omega(j-i+1)$ time, which is potentially $\Omega(|s|)$. Our strategy,
instead, is to just “mark” the subtrees where the reversal should be carried
out, and de-amortize its cost across future operations, materializing it
slowly as we traverse the marked subtrees. To this end, we extend our FeST
data structure with a new Boolean field $x.\mathrm{rev}$ in each node $x$,
which indicates that its whole subtree should be regarded as reversed, that
is, its descending nodes should be read right-to-left, but that this update
has not yet been carried out. This field is set to false on newly created
nodes. We also add a field $x.\mathrm{fprev}$, so that if $x$ represents
$s[i..j]$, then $x.\mathrm{fprev}=\kappa(s[j]s[j-1]\cdots s[i+1]s[i])$ is the
fingerprint of the reversed string. When $x.\mathrm{rev}$ is true, the fields
of $x$ (including $x.\mathrm{fp}$ and $x.\mathrm{fprev}$) still do not reflect
the reversal.

The fields $x.\mathrm{fprev}$ must be maintained all the time in the same way
as the fields $x.\mathrm{fp}$. Concretely, upon every update where the
children of node $x$ change, we not only recompute $x.\mathrm{fp}$ as shown in
Section 3.1, but also $x.\mathrm{fprev}=((x.\mathrm{right}.\mathrm{fprev}\cdot
b+x.\mathrm{char})\cdot
x.\mathrm{left}.\mathrm{power}+x.\mathrm{left}.\mathrm{fprev})\bmod p$.

In order to apply the described reversal to a substring $s[i..j]$, we first
compute $y=\texttt{isolate}(i,j)$ on the tree of $s$, and then toggle the
Boolean value $y.\mathrm{rev}=\neg\leavevmode\nobreak\ y.\mathrm{rev}$ (note
that, if $y$ had already an unprocessed reversal, this is undone without ever
materializing it). The operation reverse then takes ${\cal O}(\log|s|)$
amortized time, dominated by the cost of $\texttt{isolate}(i,j)$. We must,
however, adapt all the other operations to handle potentially reversed nodes.

#### Fixing marked nodes.

The idea is that every time we access a tree node, if it is marked as
reversed, we fix it, after which it can be treated as a regular node because
its fields will already reflect the reversal of its represented string (though
some descendant nodes may still need fixing).

Fixing a node involves exchanging its left and right children, toggling their
reverse marks, and updating the node fingerprint. More precisely, we define
the primitive $\texttt{fix}(x)$ as follows: if $x.\mathrm{rev}$ is
$\mathit{true}$, then (i) set $x.\mathrm{rev}=\mathit{false}$,
$x.\mathrm{left}.\mathrm{rev}=\neg\leavevmode\nobreak\
x.\mathrm{left}.\mathrm{rev}$,
$x.\mathrm{right}.\mathrm{rev}=\neg\leavevmode\nobreak\
x.\mathrm{right}.\mathrm{rev}$, (ii) swap $x.\mathrm{left}$ with
$x.\mathrm{right}$, and (iii) swap $x.\mathrm{fp}$ with $x.\mathrm{fprev}$. It
is easy to see that fix maintains the invariants about the meaning of the
reverse fields.

Because all the operations in splay trees, including the splay, are done along
paths that are first traversed downwards from the root, it suffices that we
run $\texttt{fix}(x)$ on every node $x$ we find as we descend from the root
(for example, on every node $x$ where we perform $\texttt{find}(x,i)$), before
taking any other action on the node. This ensures that all the accesses and
structural changes to the splay tree are performed over fixed nodes, and
therefore no algorithm needs further changes. For example, when we perform
$\textit{splay}(x)$, all the ancestors of $x$ are already fixed. As another
example, if we run equal as in Section 3.6, the nodes $y_{1}$ and $y_{2}$ will
already be fixed by the time we read their fingerprint fields. As a third
example, if we run $\texttt{retrieve}(s,i,j)$ as in Section 3.3 and the
subtree of $y$ has reversed nodes inside, we will progressively fix all those
nodes as we traverse the subtree, therefore correctly retrieving $s[i..j]$
within ${\cal O}(j-i+1)$ time.

Note that fix takes constant time and does not change the potential function
$\Phi$, so no time complexities change due to our adjustments. The new fields
also enable other queries, e.g. to decide whether a strings is a palindrome.

##  5 Conclusion

We presented a new data structure, a forest of enhanced splay trees (FeST), to
handle collections of dynamic strings. Our solution is much simpler than
existing ones, while meeting the times for most update and query operations,
albeit in most cases in amortized rather than worst-case time. Our data
structure answers queries correctly whp and updates are always correct, while
some existing solutions answer queries always correctly but succeed in the
updates whp.

To build our data structure, we employ a completely different approach from
existing solutions: we use a splay tree for representing each string,
enhancing it with a number of additional annotations. The idea of using binary
search trees, even though mentioned in the literature, has hitherto been
underrated in our opinion. As our FeST is easy to understand and to implement,
we believe that it offers the opportunity of wide usability. Further, we have
found nontrivial—yet perfectly implementable—solutions to relevant queries,
like computing the length $\ell$ of the longest common prefix of two suffixes
in time ${\cal O}(\log n+\log^{2}\ell)$ instead of the trivial ${\cal
O}(\log^{2}n)$. The simplicity of our solution enables new features, like the
possibility of reversing a substring, or reverse-complementing it, in
logarithmic amortized time. Our data structure also allows handling circular
strings, as well as omega-extensions of strings—features competing solutions
do not offer. Details will be included in the full version of the paper (and
can be found in the Appendix).

## References

  * [1] Stephen Alstrup, Gerth Stølting Brodal, and Theis Rauhe.  Pattern matching in dynamic texts.  In Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 819–828, 2000.
  * [2] Amihood Amir, Itai Boneh, Panagiotis Charalampopoulos, and Eitan Kondratovsky.  Repetition detection in a dynamic string.  In Proc. 27th Annual European Symposium on Algorithms (ESA), pages 5:1–5:18, 2019.
  * [3] Amihood Amir, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Solon P. Pissis, and Jakub Radoszewski.  Longest common factor after one edit operation.  In Proc. 24th Int’l Symposium on String Processing and Information Retrieval (SPIRE), pages 14–26, 2017.
  * [4] Amihood Amir, Panagiotis Charalampopoulos, Solon P. Pissis, and Jakub Radoszewski.  Dynamic and internal longest common substring.  Algorithmica, 82(12):3707–3743, 2020.
  * [5] Lorraine A.K. Ayad and Solon P. Pissis.  MARS: Improving multiple circular sequence alignment using refined sequences.  BMC Genomics, 18(1):1–10, 2017.
  * [6] Vineet Bafna and Pavel A. Pevzner.  Genome rearrangements and sorting by reversals.  In Proc. 34th Annual Symposium on Foundations of Computer Science (FOCS), pages 148–157, 1993.
  * [7] Hans-Juergen Boehm, Russell R. Atkinson, and Michael F. Plass.  Ropes: An alternative to strings.  Software Practice and Experience, 25(12):1315–1330, 1995.
  * [8] Christina Boucher, Davide Cenzato, Zsuzsanna Lipták, Massimiliano Rossi, and Marinella Sciortino.  Computing the original eBWT faster, simpler, and with less memory.  In Proc. 28th Int’l Symp. on String Processing and Information Retrieval (SPIRE), pages 129–142, 2021.
  * [9] Christina Boucher, Davide Cenzato, Zsuzsanna Lipták, Massimiliano Rossi, and Marinella Sciortino.  r-Indexing the eBWT.  In Proc. 28th Int’l Symposium on String Processing and Information Retrieval (SPIRE), pages 3–12, 2021.
  * [10] Alberto Caprara.  Sorting by reversals is difficult.  In Proc. 1st Annual Int’l Conference on Research in Computational Molecular Biology (RECOMB), pages 75–83, 1997.
  * [11] Alberto Caprara and Romeo Rizzi.  Improved approximation for breakpoint graph decomposition and sorting by reversals.  Journal of Combinatorial Optimization, 6(2):157–182, 2002.
  * [12] Giulio Cerbai and Luca S. Ferrari.  Permutation patterns in genome rearrangement problems: The reversal model.  Discrete Applied Mathematics, 279:34–48, 2020.
  * [13] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Shay Mozes.  Dynamic string alignment.  In Proc. 31st Annual Symposium on Combinatorial Pattern Matching (CPM), pages 9:1–9:13, 2020.
  * [14] Panagiotis Charalampopoulos, Tomasz Kociumaka, Jakub Radoszewski, Solon P. Pissis, Wojciech Rytter, Tomasz Walen, and Wiktor Zuba.  Approximate circular pattern matching.  In Proc. 30th Annual European Symposium on Algorithms (ESA), pages 35:1–35:19, 2022.
  * [15] Raphaël Clifford, Allan Grønlund, Kasper Green Larsen, and Tatiana Starikovskaya.  Upper and lower bounds for dynamic data structures on strings.  In Proc. 35th Symposium on Theoretical Aspects of Computer Science (STACS), pages 22:1–22:14, 2018.
  * [16] Richard Cole.  On the dynamic finger conjecture for splay trees. Part II: The proof.  SIAM Journal on Computing, 30(1):44–85, 2000.
  * [17] Guillaume Fertin, Anthony Labarre, Irena Rusu, Eric Tannier, and Stéphane Vialette.  Combinatorics of Genome Rearrangements.  MIT Press, 2009.
  * [18] Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Longest substring palindrome after edit.  In Proc. 29th Annual Symposium on Combinatorial Pattern Matching (CPM), pages 12:1–12:14, 2018.
  * [19] Pawel Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Lacki, and Piotr Sankowski.  Optimal dynamic strings.  CoRR, abs/1511.02612, 2015.
  * [20] Pawel Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Lacki, and Piotr Sankowski.  Optimal dynamic strings.  In Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1509–1528, 2018.
  * [21] Roberto Grossi, Costas S. Iliopoulos, Jesper Jansson, Zara Lim, Wing-Kin Sung, and Wiktor Zuba.  Finding the cyclic covers of a string.  In Proc. 17th International Conference and Workshops on Algorithms and Computation (WALCOM), pages 139–150, 2023.
  * [22] Roberto Grossi, Costas S Iliopoulos, Robert Mercas, Nadia Pisanti, Solon P Pissis, Ahmad Retha, and Fatima Vayani.  Circular sequence comparison: algorithms and applications.  Algorithms for Molecular Biology, 11(1):1–14, 2016.
  * [23] Yijie Han.  Improving the efficiency of sorting by reversals.  In Proc. Int’l Conference on Bioinformatics & Computational Biology (BIOCOMP), pages 406–409, 2006.
  * [24] Sridhar Hannenhalli and Pavel A. Pevzner.  Transforming cabbage into turnip: Polynomial algorithm for sorting signed permutations by reversals.  In Proc. 27th Annual ACM Symposium on Theory of Computing (STOC), pages 178–189, 1995.
  * [25] Costas S. Iliopoulos, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen, and Wiktor Zuba.  Linear-time computation of cyclic roots and cyclic covers of a string.  In Proc. 34th Annual Symposium on Combinatorial Pattern Matching (CPM), pages 15:1–15:15, 2023.
  * [26] Richard M. Karp and Michael O. Rabin.  Efficient randomized pattern-matching algorithms.  IBM Journal of Research and Development, 31(2):249–260, 1987.
  * [27] M. Lothaire.  Applied Combinatorics on Words.  Cambridge University Press, 2005.
  * [28] Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, and Marinella Sciortino.  An extension of the Burrows-Wheeler transform.  Theoretical Computer Science, 387(3):298–312, 2007.
  * [29] Kurt Mehlhorn, Rajamani Sundar, and Christian Uhrig.  Maintaining dynamic sequences under equality tests in polylogarithmic time.  Algorithmica, 17(2):183–198, 1997.
  * [30] Kevin Menard, Chris Seaton, and Benoit Daloze.  Specializing ropes for ruby.  In Proc. 15th Int’l Conf. on Managed Languages & Runtimes (ManLang), pages 10:1–10:7, 2018.
  * [31] Gonzalo Navarro and Nicola Prezza.  Universal compressed text indexing.  Theoretical Computer Science, 762:41–50, 2019.
  * [32] Andre Rodrigues Oliveira, Ulisses Dias, and Zanoni Dias.  On the sorting by reversals and transpositions problem.  Journal of Universal Computer Science, 23(9):868–906, 2017.
  * [33] Daniel Dominic Sleator and Robert Endre Tarjan.  Self-adjusting binary search trees.  Journal of the ACM, 32(3):652–686, 1985.
  * [34] Damien Stehlé and Paul Zimmermann.  A binary recursive gcd algorithm.  In Proc. 6th Int’l Symposium on Algorithmic Number Theory (ANTS), pages 411–425, 2004.
  * [35] Rajamani Sundar and Robert E. Tarjan.  Unique binary-search-tree representations and equality testing of sets and sequences.  SIAM Journal on Computing, 23(1):24–44, 1994.
  * [36] Wojciech Szpankowski.  A generalized suffix tree and its (un)expected asymptotic behaviors.  SIAM Journal on Computing, 22(6):1176–1198, 1993.
  * [37] Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Longest Lyndon substring after edit.  In Proc. 29th Annual Symposium on Combinatorial Pattern Matching (CPM), pages 19:1–19:10, 2018.
  * [38] G.A. Watterson, W.J. Ewens, T.E. Hall, and A. Morgan.  The chromosome inversion problem.  Journal of Theoretical Biology, 99:1–7, 1982.

## APPENDIX

##  Appendix A Figures

$j$splay $\textit{node}(j+1)$$i$splay
$\textit{node}(i-1)$$i-1$$j+1$$i$$j$$i$$j+1$

(a) General sequence of operations for $\mathtt{isolate}(i,j)$.

$j+1$$p$$i-1$$A$$D$$B$$C$rotate($\textit{node}(i-1$),$p$)$i-1$$A$$B$$j+1$$C$$D$$p$rotate($\textit{node}(i-1$),
$\leavevmode\nobreak\
\textit{node}(j+1$))$i-1$$B$$A$$j+1$$C$$D$$p$$i$$j$$i$$j$$i$$j$

(b) Case of zig-zag as the last splaying operation for
$\mathtt{isolate}(i,j)$.

$j+1$$y$$i-1$$A$$D$$C$$B$rotate($\textit{node}(i-1$),$y$)$i-1$$A$$B$$j+1$$C$$D$$y$rotate($\textit{node}(i-1$),
$\leavevmode\nobreak\
\textit{node}(j+1$))$i-1$$A$$B$$j+1$$C$$D$$y$$i$$j$$i$$j$$i$$j$

(c) Case of the modified zig-zig as the last splaying operation for
$\mathtt{isolate}(i,j)$.

Figure 1:  Scheme of the $\mathtt{isolate}(i,j)$ operation applied on a splay
tree. Subfigures 1(b) and 1(c) show two cases of the last splay operation of
$\mathtt{isolate}(i,j)$, yielding a single (shaded) subtree that represents
the substring $s[i..j]$.

$\ell^{\prime}$$\mathtt{extract}(s_{1},i_{1},i_{1}{+}\ell^{\prime}{-}1)$$\ell^{\prime}$exponential
search$\ell^{\prime}$$\ell$$i_{1}$re-introduce

Figure 2: Scheme of operations for lcp shown on one of the two strings.

$x$$A$$B$$x.\mathrm{rev}=\textit{true}$toggle
rev$x$$A$$B$$\textit{root}(A).\mathrm{rev}=$$\neg\textit{root}(A).\mathrm{rev}$swap
left-rightand $x.\mathrm{fp}$ with
$x.\mathrm{fprev}$$x$$B$$A$$x.\mathrm{rev}=\textit{false}$$\textit{root}(B).\mathrm{rev}=$$\neg\textit{root}(B).\mathrm{rev}$$x.\mathrm{fp}\leftrightarrow
x.\mathrm{fprev}$

Figure 3: Scheme of the fix operation on node $x$.

$s=$mississippim s s p i i s i s i
p$\mathtt{extract}(s,9,11)$$s=$mississi$s^{\prime}=$ppim s s p i i s i s i
p$\mathtt{introduce}(s,1,s^{\prime})$m i i s s s$s=\text{ppimississi}$ p i p i
s

Figure 4: Cycle-rotation operation: rotate$(s,9)$ moves $s[9..]$ to the left
of $s[..8]$. After the rotation the string becomes $s[9..]s[..8]$.

##  Appendix B String uniqueness

Our string collections allow the existence of repeated dynamic strings. While
debatable in a static scenario, this makes all the sense in the dynamic case,
since those strings that are equal at some moment may undergo different
updates later. If for some reason we wanted to ensure uniqueness (whp), we
could maintain a balanced tree with the root fingerprints
$\textit{root}(T).\mathrm{fp}$ of all the trees $T$ of the FeST. Every string
creation or update would then check the tree for uniqueness, increasing the
cost by ${\cal O}(\log M)$, where $M\leq N$ is the number of strings in the
collection.

##  Appendix C Involutions

Operation $\texttt{map}(s,i,j)$, applying a (fixed) involution $f$ to the
symbols in $s[i..j]$, can be implemented analogously to substring reversals,
that is, isolating $s[i..j]$ in a node $y=\texttt{isolate}(i,j)$ and then
marking that the substring covered by node $y$ is mapped using a new Boolean
field $y.\mathrm{map}$, which is set to true. This will indicate that every
symbol $s[k]$, for $i\leq k\leq j$, must be interpreted as $f(s[k])$, but that
the change has not yet been materialized. Similarly to reverse, this
information will be propagated downwards whenever we descend into a subtree,
otherwise it is maintained in the subtree’s root only. The operation will then
take ${\cal O}(\log|s|)$ amortized time.

To manage the mapping and deamortize its linear cost across subsequent
operations, we will also store fields
$x.\mathrm{mfp}=\kappa(f(s[i])f(s[i+1])\cdots f(s[j]))$ and
$x.\mathrm{mfprev}=\kappa(f(s[j])f(s[j-1])\cdots f(s[i]))$, which maintain the
fingerprint of the mapped string, and its reverse, represented by $x$. Those
are maintained analogously as the previous fingerprints: (1)
$x.\mathrm{mfp}=((x.\mathrm{left}.\mathrm{mfp}\cdot b+f(x.\mathrm{char}))\cdot
x.\mathrm{right}.\mathrm{power}+x.\mathrm{right}.\mathrm{mfp})\bmod p$, and
(2) $x.\mathrm{mfprev}=((x.\mathrm{right}.\mathrm{mfprev}\cdot
b+f(x.\mathrm{char}))\cdot
x.\mathrm{left}.\mathrm{power}+x.\mathrm{left}.\mathrm{mfprev})\bmod p$.

As for string reversals, every time we access a tree node, if it is marked as
mapped, we unmark it and toggle the mapped mark of its children, before
proceeding with any other action. Precisely, we define the primitive
$\texttt{fixm}(x)$ as follows: if $x.\mathrm{map}$ is $\mathit{true}$, then
(i) set $x.\mathrm{map}=\mathit{false}$,
$x.\mathrm{left}.\mathrm{map}=\neg\leavevmode\nobreak\
x.\mathrm{left}.\mathrm{map}$,
$x.\mathrm{right}.\mathrm{map}=\neg\leavevmode\nobreak\
x.\mathrm{right}.\mathrm{map}$, (ii) set $x.\mathrm{char}=f(x.\mathrm{char})$,
and (iii) swap $x.\mathrm{fp}$ with $x.\mathrm{mfp}$, and $x.\mathrm{fprev}$
with $x.\mathrm{mfprev}$. We note that, in addition, the fix operation defined
in Section 4.2 must also exchange $x.\mathrm{mfp}$ with $x.\mathrm{mfprev}$ if
we also support involutions. Note how, as for reversals, two applications of
$f$ cancel each other, which is correct because $f$ is an involution.
Operation fixm is applied in the same way as fix along tree traversals.

#### Reverse complementation.

By combining string reversals and involutions, we can for example support the
application of reverse complementation of substrings in DNA sequences, where a
substring $s[i..j]$ is reversed and in addition its symbols are replaced by
their Watson-Crick complement, applying the involution
$f(\mathtt{A})=\mathtt{T}$, $f(\mathtt{T})=\mathtt{A}$,
$f(\mathtt{C})=\mathtt{G}$, and $f(\mathtt{G})=\mathtt{C}$. In case we only
want to perform reverse complementation (and not reversals and involutions
independently), we can simplify our fields and maintain only a Boolean field
$x.\mathrm{rc}$ and the fingerprint $x.\mathrm{mfprev}$ in addition to
$x.\mathrm{fp}$. Fixing a node consists of: if $x.\mathrm{rc}$ is
$\mathit{true}$, then (i) set $x.\mathrm{rc}=\mathit{false}$,
$x.\mathrm{left}.\mathrm{rc}=\neg\leavevmode\nobreak\
x.\mathrm{left}.\mathrm{rc}$,
$x.\mathrm{right}.\mathrm{rc}=\neg\leavevmode\nobreak\
x.\mathrm{right}.\mathrm{rc}$, (ii) set $x.\mathrm{char}=f(x.\mathrm{char})$,
(iii) swap $x.\mathrm{left}$ with $x.\mathrm{right}$, (iv) swap
$x.\mathrm{fp}$ with $x.\mathrm{mfprev}$.

##  Appendix D Circular strings and omega extensions

###  D.1 Additional definitions

In this section, we are going to use some further concepts regarding
conjugacy.

Two strings $s,t$ are conjugates if there exist strings $u,v$, possibly empty,
such that $s=uv$ and $t=vu$. Conjugacy is an equivalence; the equivalence
classes $[s]$ are also called circular strings, and any $t\in[s]$ is called a
linearization of this circular string. Abusing notation, any linear string $s$
can be viewed as a circular string, in which case it is taken as a
representative of its conjugacy class. A substring of a circular string $s$ is
any prefix of any $t\in[s]$, or, equivalently, a string of the form $s[i..j]$
for $1\leq i,j\leq|s|$ (a linear substring), or $s[i..]s[..j]$, where $j<i$. A
necklace is a string $s$ with the property that $s\leq_{{\textrm{lex}}}t$ for
all $t\in[s]$. Every conjugacy class contains exactly one necklace.

When the dynamic strings in our collection are to be interpreted as circular
strings, we need to adjust some of our operations. Our model is that we will
maintain a canonical representative $\hat{s}$ of the class of rotations of
$s$. All the indices of the operations refer to positions in $\hat{s}$.
Internally, we may store in the FeST another representative $s$ of the class,
not necessarily $\hat{s}$.

###  D.2 Circular strings

Our general approach to handle operations on $\hat{s}$ regarding it as
circular is to rotate it conveniently before accessing it. The splay tree $T$
of $\hat{s}$ will then maintain some (string) rotation
$s=\hat{s}[r..]\hat{s}[..r-1]$ of $\hat{s}$, and we will maintain a field
$\mathrm{start}(\hat{s})=r$ so that we can map any index $\hat{s}[i]$ referred
to in update or query operations to
$s[((|s|+i-\mathrm{start}(\hat{s}))\bmod|s|)+1]$.

When we want to change the rotation of $\hat{s}$ to another index
$r^{\prime}$, so that we now store
$s^{\prime}=\hat{s}[r^{\prime}..]\hat{s}[..r^{\prime}-1]$, we make use of a
new operation $\texttt{rotate}(s,i)$, which rotates $s$ so that its splay tree
represents $s[i..]s[..i-1]$. This is implemented as
$s^{\prime}=\texttt{extract}(s,i,|s|)$ followed by
$\texttt{introduce}(s,1,s^{\prime})$. We then move from rotation $r$ to
$r^{\prime}$ in ${\cal O}(\log|s|)$ amortized time by doing
$\texttt{rotate}(s,r^{\prime}-r+1)$ if $r^{\prime}>r$, or
$\texttt{rotate}(s,|s|+r^{\prime}-r+1)$ if $r^{\prime}<r$. We then set
$\mathrm{start}(\hat{s})=r^{\prime}$.

Operation $s=\texttt{make-string}(w)$ stays as before, in the understanding
that $\hat{s}=w$ will be seen as the canonical representation of the class, so
we set $\mathrm{start}(\hat{s})=1$; this can be changed later with a string
rotation if desired. All the operations that address a single position
$\hat{s}[i]$, like access and the edit operations, are implemented verbatim by
just shifting the index $i$ using $\mathrm{start}(\hat{s})$ as explained.
Instead, the operations retrieve, extract, equal, reverse, and map, which act
on a range $\hat{s}[i..j]$, may give trouble when $i>j$, as in this case the
substring is $\hat{s}[i..]\hat{s}[..j]$ by circularity. In this case, those
operations will be preceded by a change of rotation from the current one,
$r=\mathrm{start}(\hat{s})$, to $r^{\prime}=1$, using rotate as explained.
This guard will get rid of those cases. Note that, in the case of equal, we
may need to rotate both $s_{1}$ and $s_{2}$, independently, to compute each of
the two signatures.

The two remaining operations deserve some consideration. Operation
$\texttt{introduce}(s_{1},i,s_{2})$ could be implemented verbatim (with the
shifting of $i$), but in this case it would introduce in $\hat{s_{1}}[i]$ the
current rotation of $s_{2}$, instead of $\hat{s_{2}}$ as one would expect.
Therefore, we precede the operation by a change of rotation in $s_{2}$ to
$r^{\prime}=1$, which makes the splay tree store $\hat{s_{2}}$ with
$\mathrm{start}(\hat{s_{2}})=1$.

Finally, in operation $\texttt{lcp}(s_{1},i_{1},s_{2},i_{2})$ we do not know
for how long the LCP will extend, so we precede it by changes of rotations in
both $s_{1}$ and $s_{2}$ that make them start at position $1$ of $\hat{s_{1}}$
and $\hat{s_{2}}$. In case $s_{1}=s_{2}$, however, this trick cannot be used.
One simple solution is to rotate the string every time we call equal during
Step 1; recall Section 4.1. This will be needed as long as the accesses are
done on $s_{1}$ and $s_{2}$; as soon as we extract the substrings of length
$\ell^{\prime\prime}$ (and, later, $\ell^{\prime}$ for Step 3), we work only
on the extracted strings. While the complexity is preserved, rotating the
string every time can be too cumbersome. We can use an alternative way to
compute signatures of circular substrings, $\kappa(s[i..]s[..j])$: we compute
as in Section 3.6 $\sigma=\kappa(s[i..])$ and $\tau=\kappa(s[..j])$, as well
as $b^{j}\bmod p$, which comes for free with the computation of $\tau$; then
$\kappa(s[i..]s[..j])=(\sigma\cdot b^{j}+\tau)\bmod p$.

Overall, we maintain for all the operations the same asymptotic running times
given in the Introduction when the strings are interpreted as circular.

#### Signed reversals on circular strings.

By combining reversals and involutions, we can support signed reversals on
circular strings, too. We do this in the same way as for linear strings,
namely by doubling the alphabet $\Sigma$ of gene identifiers such that each
gene $i$ has a negated version $-i$, and using the involution $f(i)=-i$ (and
$f(-i)=i$). Note that the original paper in which reversals were introduced
[38] used circular chromosomes.

###  D.3 Omega extensions

Circular dynamic strings allow us to implement operations that act on the
omega extensions of the underlying strings. Recall that for a (linear) string
$s$, the infinite string $s^{\omega}$ is defined as the infinite concatenation
$s^{\omega}=s\cdot s\cdot s\cdots$. These are, for example, used in the
definition of the extended Burrows-Wheeler Transform (eBWT) of Mantaci et al.
[28], where the underlying string order is based on omega extensions. In this
case, comparisons of substrings may need to be made whose length exceeds the
shorter of the two strings $s_{1}$ and $s_{2}$. We therefore introduce a
generalization of circular substrings as follows: $t$ is called an omega-
substring of $s$ if $t=s[i..]s^{k}s[..j]$ for some $j<i-1$ and $k\geq 0$. Note
that the suffix $s[i..]$ and the prefix $s[..j]$ may also be empty. Thus, $t$
is an omega-substring of $s$ if and only if $t=v^{k}v[..j]$ for some $k\geq 1$
and some conjugate $v$ of $s$.

An important tool in this section will be the famous Fine and Wilf Lemma [27],
which states that if a string $w$ has two periods $r,q$ and $|w|\geq
r+q-\gcd(r,q)$, then $w$ is also periodic with period $\gcd(r,q)$. The
following is a known corollary, a different formulation of which was proven,
e.g., in [28]; we reprove it here for completeness.

######  Lemma D.1.

Let $u,v$ be two strings. If
$\mathrm{lcp}(u^{\omega},v^{\omega})\geq|u|+|v|-\gcd(|u|,|v|)$, then
$u^{\omega}=v^{\omega}$.

######  Proof D.2.

Let $\ell=\mathrm{lcp}(u^{\omega},v^{\omega})\geq|u|+|v|-\gcd(|u|,|v|)$. Then
the string $t=s_{1}^{\omega}[..\ell]$ is periodic both with period $|u|$ and
with period $|v|$, and thus, by the Fine and Wilf lemma, it is also periodic
with period $\gcd(|u|,|v|)$. Since $\gcd(|u|,|v|)\leq|u|,|v|$, this implies
that both $u$ and $v$ are powers of the same string $x$, of length
$\gcd(|u|,|v|)$ and therefore, $u^{\omega}=x^{\omega}=v^{\omega}$.

We further observe that the fingerprint of strings of the form $u^{k}$ can be
computed from the fingerprint of string $u$. More precisely, let $u$ be a
string, $\pi=\kappa(u)$ its fingerprint, and $k\geq 1$. Then, calling
$d=b^{|u|}\bmod p$ (which we also obtain in the field $y.\mathrm{power}$ when
computing $\kappa(u)$), it holds

$\displaystyle\kappa(u^{k})$ $\displaystyle=$ $\displaystyle(\pi\cdot
d^{k-1}+\pi\cdot d^{k-2}+\cdots+\pi\cdot d+\pi)\bmod p$ (1) $\displaystyle=$
$\displaystyle(\pi\cdot(d^{k-1}+d^{k-2}+\cdots+1))\bmod p,$

where $\textit{geomsum}(d,k-1)=(d^{k-1}+d^{k-2}+\cdots+1)\bmod p$ can be
computed in ${\cal O}(\log k)$ time using the identity
$d^{2k+1}+d^{2k}+\cdots+1=(d+1)\cdot((d^{2})^{k}+(d^{2})^{k-1}+\cdots+1)$, as
follows555This technique seems to be folklore. Note that the better known
formula $\textit{geomsum}(d,k)=((d^{k+1}-1)\cdot(d-1)^{-1})\bmod p$ requires
computing multiplicative inverses, which takes ${\cal O}(\log N)$ time using
the extended Euclid’s algorithm, or ${\cal O}(\log\log N)$ with faster
algorithms [34]; those terms would not be absorbed by others in our cost
formula. (all modulo $p$):

$\displaystyle\textit{geomsum}(d,0)$ $\displaystyle=$ $\displaystyle 1$
$\displaystyle\textit{geomsum}(d,2k+1)$ $\displaystyle=$
$\displaystyle(d+1)\cdot\textit{geomsum}(d^{2},k)$ (2)
$\displaystyle\textit{geomsum}(d,2k)$ $\displaystyle=$ $\displaystyle
d\cdot\textit{geomsum}(d,2k-1)+1$

#### Extended substring equality.

We devise at least two ways in which our equal query can be extended to omega
extensions. First, consider the query
$\texttt{equal}_{\omega}(s_{1},i_{1},s_{2},i_{2},\ell)=\texttt{equal}(s_{1}^{\omega},i_{1},s_{2}^{\omega},i_{2},\ell)$,
that is, the normal substring equality interpreted on the omega extensions of
$s_{1}$ and $s_{2}$. We let $v_{1}=\texttt{rotate}(s_{1},i_{1})$ and
$v_{2}=\texttt{rotate}(s_{2},i_{2})$. Then we have
$s_{1}^{\omega}[i_{1}..i_{1}+\ell-1]=v_{1}^{k_{1}}v_{1}[..j_{1}]$, where
$k_{1}=\lfloor\ell/|s_{1}|\rfloor$ and $j_{1}=\ell\bmod|s_{1}|$. If $k_{1}=0$,
we simply compute
$\kappa_{1}=\kappa(s_{1}^{\omega}[i_{1}..i_{1}+\ell-1])=\kappa(v_{1}[..j_{1}])$.
Otherwise, we compute $\kappa_{1}=\kappa(s_{1}^{\omega}[i_{1}..i_{1}+\ell-1])$
by applying Eq. (1) as follows:

$\displaystyle\kappa_{1}=(\kappa(v_{1})\cdot(d^{k_{1}-1}+\cdots+1)\cdot
b^{j_{1}}+\kappa(v_{1}[..j_{1}]))\bmod p.$ (3)

There are various components to compute in this formula apart from the
fingerprints themselves. First, note that $d=b^{|s_{1}|}\bmod
p=b^{|v_{1}|}\bmod p=\textit{root}(T_{1}).\mathrm{power}$ for the tree $T_{1}$
of $s_{1}$ (or $v_{1}$), so we have it in constant time. Second,
$b^{j_{1}}\bmod p$ is the field $y.\mathrm{power}$ after we compute
$\kappa(v_{1}[..j_{1}])$ via $y=\texttt{isolate}(v_{1},1,j_{1})$ after
completion of rotate($s_{1},i_{1}$), thus we also have it in constant time.
Third, $d^{k_{1}-1}+\cdots+1=\textit{geomsum}(d,k_{1}-1)$ is computed with Eq.
(2) in time ${\cal O}(\log k_{1})\subseteq{\cal O}(\log\ell)$.

By Lemma D.1 we can define $\ell_{\omega}=|s_{1}|+|s_{2}|$ and, if
$\ell\geq\ell_{\omega}$, run the $\texttt{equal}_{\omega}$ query with
$\ell_{\omega}$ instead of $\ell$. The lemma shows that
$s_{1}[i_{1}..i_{1}+\ell-1]=s_{2}[i_{2}..i_{2}+\ell-1]$ iff
$s_{1}[i_{1}..i_{1}+\ell_{\omega}-1]=s_{2}[i_{2}..i_{2}+\ell_{\omega}-1]$.
This limits $\ell$ to $|s_{1}|+|s_{2}|$ in our query and therefore the cost
${\cal O}(\log\ell)$ is in ${\cal O}(\log|s_{1}s_{2}|)$.

We compute $\kappa_{2}$ analogously, and return true if and only if
$\kappa_{1}=\kappa_{2}$, after undoing the rotations to get back the original
strings $s_{1}$ and $s_{2}$. The total amortized time for operation
$\texttt{equal}_{\omega}$ is then ${\cal O}(\log|s_{1}s_{2}|)$. Note that our
results still hold whp because we are deciding on fingerprints of strings of
length ${\cal O}(N)$, not ${\cal O}(\ell)$ (which is in principle unbounded).

A second extension of equal is
$\texttt{equal}_{\omega}^{\omega}(s_{1},i_{1},\ell_{1},s_{2},i_{2},\ell_{2})$,
interpreted as
$(s_{1}^{\omega}[i_{1}..i_{1}+\ell_{1}-1])^{\omega}=(s_{2}^{\omega}[i_{2}..i_{2}+\ell_{2}-1])^{\omega}$,
that is, the omega extension of $s_{1}^{\omega}[i_{1}..i_{1}+\ell_{1}-1]$ is
equal to the omega extension of $s_{2}^{\omega}[i_{2}..i_{2}+\ell_{2}-1]$. By
Lemma D.1, this is equivalent to
$(s_{1}^{\omega}[i_{1}..i_{1}+\ell_{1}-1])^{\ell_{2}}=(s_{2}^{\omega}[i_{2}..i_{2}+\ell_{2}-1])^{\ell_{1}}$.
So we first compute
$\kappa_{1}=\kappa(s_{1}^{\omega}[i_{1}..i_{1}+\ell_{1}-1])$ and
$\kappa_{2}=\kappa(s_{2}^{\omega}[i_{2}..i_{2}+\ell_{2}-1])$ as above, compute
$d_{1}=b^{\ell_{1}}\bmod p$ and $d_{2}=b^{\ell_{2}}\bmod p$, and then return
whether $(\kappa_{1}\cdot(d_{1}^{\ell_{2}-1}+\cdots+1))\bmod
p=(\kappa_{2}\cdot(d_{2}^{\ell_{1}-1}+\cdots+1))\bmod p$. Operation
$\texttt{equal}_{\omega}^{\omega}$ is then also computed in amortized time
${\cal O}(\log|s_{1}s_{2}|)$.

#### Extended longest common prefix.

We are also able to extend LCPs to omega extensions: operation
$\texttt{lcp}_{\omega}(s_{1},i_{1},s_{2},i_{2})$ computes, for the
corresponding rotations $v_{1}=\texttt{rotate}(s_{1},i_{1})$ and
$v_{2}=\texttt{rotate}(s_{2},i_{2})$, the longest common prefix length
lcp($v_{1}^{\omega},v_{2}^{\omega}$), as well as the lexicographic order of
$v_{1}^{\omega}$ and $v_{2}^{\omega}$. That this can be done efficiently
follows again from Lemma D.1. We first compare their omega-substrings of
length $\ell_{\omega}=|s_{1}|+|s_{2}|$. If
$\texttt{equal}_{\omega}(s_{1},i_{1},s_{2},i_{2},\ell_{\omega})$ answers true,
then it follows that $\texttt{lcp}(s_{1},i_{1},s_{2},i_{2})$ is $\infty$.
Otherwise, we run a close variant of the algorithm described in Section 4.1;
note that $\ell_{\omega}$ can be considerably larger than one of $s_{1}$ or
$s_{2}$. For Step 1, we define $n^{\prime}=n=|s_{1}s_{2}|$; the other formulas
do not change. We run the $\texttt{equal}_{\omega}$ computations on $s_{1}$
and $s_{2}$ using Eq. (3) to compute the fingerprints. We extract the
substrings of length $\ell^{\prime}$ in Step 3 (analogously,
$\ell^{\prime\prime}$ in Step 1) using the extract for circular strings, but
do so only if $\ell^{\prime}\leq|s_{1}|$ (resp., $\ell^{\prime}\leq|s_{2}|)$;
otherwise we keep accessing the original string using Eq. (3). The total
amortized time to compute LCPs on omega extensions is thus ${\cal
O}(\log|s_{1}s_{2}|)$.

##  Appendix E Future work

One feature that we would like to add to our data structure is allowing
identification of conjugates. The rationale behind this is that a circular
string can be represented by any of its linearizations, so these should all be
regarded as equivalent. Furthermore, when the collection contains several
conjugates of the same string, then this may be just an artifact caused by the
data acquisition process.

This could be solved by replacing each circular string with its necklace
representative, that is, the unique conjugate that is lexicographically
minimal in the conjugacy class, before applying make-string; this
representative is computable in linear time in the string length [27].
However, updates can change the lexicographic relationship of the rotations,
and thus the necklace representative of the conjugacy class. Recomputing the
necklace rotation of $s$ after each update would add worst-case ${\cal
O}(|s|)$ time to our running times, which is not acceptable. Computing the
necklace rotation after an edit operation, or more in general, after any one
of our update operations, is an interesting research question, which to the
best of our knowledge has not yet been addressed.


# Optimal work fluctuations for thermally isolated systems in weak processes

Pierre Nazé<EMAIL_ADDRESS>Universidade Estadual Paulista, 14800-090,
Araraquara, São Paulo, Brazil

###### Abstract

The fluctuation-dissipation relation for the classical definition of work is
extended to thermally isolated systems, in classical and quantum realms. From
this, the optimal work variance is calculated, showing it achieves its minimum
possible value, independent of the rate of the process, in a so-called
quasistatic variance, related to the difference between the quasistatic work
and the difference of Helmholtz’s free energy of the system. The result is
corroborated by the example of the classical and driven harmonic oscillator,
whose probability density function of the work distribution is non-Gaussian
and constant for different rates. The optimal variance is calculated for the
quantum Ising chain as well, showing its finiteness if the linear response
validity criterion is complied. A stronger definition of the arbitrary
constant for the relaxation function of thermally isolated systems is obtained
along the work.

##  I Introduction

Fluctuation-dissipation relations are important identities able to furnish
information about optimal control of dissipated averages and fluctuations. In
the context of classical and isothermal processes, it has been shown for
quadratic potentials [1], slowly-varying [2] and weak [3] processes. Using the
quantum definition of the work, it has been shown its breakdown for slowly-
varying and weak processes [4, 5].

The aim of this work is to obtain the optimal work fluctuations of classical
and quantum thermally isolated systems using the classical definition of work.
This is done by means of an extension of the fluctuation-dissipation relation.
By contrast with the isothermal case, such a relation presents a breakdown,
presenting an extra quasistatic variance in the equality, which is independent
of the rate of the process, and related to the difference between the
quasistatic work and difference of Helmholtz’s free energy of the system. When
the protocol is optimal, the optimal variance achieves its minimal value in
this quasistatic variance. To exemplify it, it is presented the driven
harmonic oscillator. In particular, its work probability distribution is non-
Gaussian and independent of the rate. The optimal variance for the quantum
Ising chain is calculated as well, showing its finiteness if the the linear
response validity agreement is complied.

##  II Weak processes

I start defining notations and developing the main concepts to be used in this
work. This section is based on the technical introductory section of Ref. [3].

Consider a classical system with a Hamiltonian
$\mathcal{H}(\mbox{\boldmath$z$}(\mbox{\boldmath$z_{0}$},t)),\lambda(t))$,
where $\mbox{\boldmath$z$}(\mbox{\boldmath$z_{0}$},t)$ is a point in the phase
space $\Gamma$ evolved from the initial point $z_{0}$ until time $t$, with
$\lambda(t)$ being a time-dependent external parameter. Initially, the system
is at equilibrium with a heat bath of temperature
$\beta\equiv{(k_{B}T)}^{-1}$, where $k_{B}$ is Boltzmann’s constant. The heat
bath is then removed from the system, and during a switching time $\tau$, the
external parameter is changed from $\lambda_{0}$ to
$\lambda_{0}+\delta\lambda$. The average work performed on the system during
this interval of time is

$\overline{W}(\tau)\equiv\int_{0}^{\tau}\left\langle\partial_{\lambda}\mathcal{H}(t)\right\rangle_{0}\dot{\lambda}(t)dt,$
(1)

where $\partial_{\lambda}$ is the partial derivative in respect to $\lambda$
and the superscripted dot the total time derivative. The generalized force
$\left\langle\partial_{\lambda}\mathcal{H}\right\rangle_{0}$ is calculated
using the averaging $\langle\cdot\rangle_{0}$ over the initial canonical
ensemble. The external parameter can be expressed as

$\lambda(t)=\lambda_{0}+g(t)\delta\lambda,$ (2)

where to satisfy the initial conditions of the external parameter the protocol
$g(t)$ must satisfy the following boundary conditions $g(0)=0$, $g(\tau)=1$.

Linear-response theory aims to express average quantities until the first-
order of some perturbation parameter considering how this perturbation affects
the observable to be averaged and the probabilistic distribution [6]. In our
case, we consider that the parameter does not considerably change during the
process, $|g(t)\delta\lambda/\lambda_{0}|\ll 1$, for all $t\in[0,\tau]$ and
$\lambda_{0}\neq 0$. The generalized force can be approximated until the first
order as [7]

$\begin{split}\left\langle\partial_{\lambda}\mathcal{H}(t)\right\rangle_{0}=&\,\left\langle\partial_{\lambda}\mathcal{H}\right\rangle_{0}-\widetilde{\Psi}_{0}\lambda(t)\\\
&+\int_{0}^{t}\Psi_{0}(t-t^{\prime})\dot{\lambda}(t^{\prime})dt^{\prime},\end{split}$
(3)

where

$\Psi_{0}(t)=\beta\left\langle\partial_{\lambda}\mathcal{H}(0)\partial_{\lambda}\mathcal{H}(t)\right\rangle_{0}-\mathcal{C}$
(4)

is the relaxation function and
$\widetilde{\Psi}_{0}\equiv\Psi_{0}(0)-\left\langle\partial_{\lambda\lambda}^{2}\mathcal{H}\right\rangle_{0}$
[6]. The constant $\mathcal{C}$ is arbitrary, whose chosen value I am going to
discuss in the next section. Combining Eqs. (1) and (3), the average work
performed at the linear response of the generalized force is

$\begin{split}\overline{W}(\tau)=&\,\delta\lambda\left\langle\partial_{\lambda}\mathcal{H}\right\rangle_{0}-\frac{\delta\lambda^{2}}{2}\widetilde{\Psi}_{0}\\\
&+\frac{1}{2}\int_{0}^{\tau}\int_{0}^{\tau}\Psi_{0}(t-t^{\prime})\dot{\lambda}(t^{\prime})\dot{\lambda}(t)dt^{\prime}dt.\end{split}$
(5)

where the symmetric property of the relaxation function was used [6]. Such an
equation holds for finite-time and weak processes.

Our treatment throughout this work will be classical, but the same reasoning
with similar arguments leads to the same average work for quantum systems,
where the observables become operators, and averages, traces.

##  III Constant $\mathcal{C}$

In previous works, I have observed that the double integral on Eq. (5) depends
on the path, which would indicate that the other terms are the contribution of
the quasistatic work $W_{\rm qs}$. However, the constant $\mathcal{C}$ must be
chosen properly to produce such a result. For isothermal processes, it is
chosen such that the relaxation function decorrelates for long times

$\lim_{t\rightarrow\infty}\Psi_{0}(t)=0,$ (6)

which is nothing more than a feature of the Second Law of Thermodynamics.
However, for thermally isolated systems, such operation does not make any
sense, because the relaxation function does not decorrelate. One alternative
is the definition proposed by Kubo [6] where $\mathcal{C}$ is calculated such
that

$\lim_{s\rightarrow 0^{+}}s\widetilde{\Psi}_{0}(s)=0,$ (7)

where $\widetilde{\cdot}$ is the Laplace transform. This definition, in my
opinion, although the success verified a posteriori [8, 9, 10, 11], lacks an a
priori physical motivation. In what follows I propose an alternative which
will furnish a value to $\mathcal{C}$ agreeing with the Second Law of
Thermodynamics.

##  IV Cumulant series

Jarzynski’s equality is well recognized as a generalization of the Second Law
of Thermodynamics [1]. I am going to propose a definition of $\mathcal{C}$
which will agree with such a relation. According to it, it holds the following
cumulant series expansion for the irreversible work

$\beta W^{\rm irr}=\beta(\overline{W}-\Delta
F)=\sum_{n=2}^{\infty}\frac{(-\beta)^{n}}{n!}\kappa_{n},$ (8)

where $\overline{W}$ is the average work for a thermally isolated system,
$\kappa_{n}$ the cumulants for the work probability distribution and $\Delta
F$ is the difference of Helmholtz’s free energy. Writing in terms of the
excess work, one has

$\displaystyle\beta W^{\rm ex}$ $\displaystyle=\beta(\overline{W}-W_{\rm qs})$
(9)
$\displaystyle=\sum_{n=2}^{\infty}\frac{(-\beta)^{n}}{n!}\kappa_{n}+\beta(\Delta
F-W_{\rm qs})$ (10)

In particular, using linear response theory, one has

$\beta W^{\rm ex}_{2}=\frac{\beta^{2}}{2}\kappa_{2}+\beta(\Delta F-W_{\rm
qs})_{2},$ (11)

where the terms were calculated until the second order in the parameter
perturbation. Using

$\beta W^{\rm
ex}_{2}-\frac{\beta^{2}}{2}\kappa_{2}=-\beta\mathcal{C}-\frac{\beta^{2}}{2}\delta\lambda^{2}\langle\partial_{\lambda}\mathcal{H}(0)\rangle_{0}^{2}$
(12)

one has

$\beta\mathcal{C}=-\frac{\beta^{2}}{2}\delta\lambda^{2}\langle\partial_{\lambda}\mathcal{H}(0)\rangle_{0}^{2}+\beta(W_{\rm
qs}-\Delta F)_{2}.$ (13)

However, by the definitions of $\Delta F$ and $W_{\rm qs}$, one has

$\beta(W_{\rm qs}-\Delta
F)_{2}=\frac{\beta^{2}}{2}\delta\lambda^{2}\langle\partial_{\lambda}\mathcal{H}(0)\rangle_{0}^{2}.$
(14)

Therefore

$\mathcal{C}=0,$ (15)

which is a stronger and physically more meaningful definition for such a
constant than that proposed by Kubo. Such a result is corroborated by
different works, for classical and quantum systems [8, 9, 10, 11]. Using the
classical definition of work, the cumulant series can be extended using the
quantum treatment.

##  V Fluctuation-dissipation relation

From the approximation of the cumulant series for linear response theory
deduced in the previous section, observe that it holds the following
fluctuation-dissipation relation

$\beta W^{\rm
ex}_{2}=\frac{\beta^{2}}{2}\sigma^{2}_{W_{2}}-\frac{\beta^{2}\delta\lambda^{2}}{2}\langle\partial_{\lambda}\mathcal{H}(0)\rangle_{0}^{2},$
(16)

where $\sigma^{2}_{W_{2}}$ is the variance of the work probability
distribution calculated until the second-order in the parameter perturbation.
That relation implies that the excess work expends less energy than its
irreversible work counterpart. The breakdown in the relation when compared to
isothermal cases occurs due to the difference between the quasistatic work and
the difference of Helmholtz’s free energy.

To exemplify such a result, consider a linear-driven harmonic oscillator,
whose Hamiltonian is

$\mathcal{H}(\lambda(t))=\frac{p^{2}}{2}+\lambda(t)\frac{q^{2}}{2},$ (17)

where $\lambda(t)=\lambda_{0}+\delta\lambda(t/\tau)$. Its solution is known
for the full dynamics, from where the average work and work variance can be
calculated. Also, the quasistatic work is known [8]

$W_{\rm
qs}=\frac{1}{\beta}\left(\sqrt{\frac{\lambda_{0}+\delta\lambda}{\lambda_{0}}}-1\right).$
(18)

Considering $\delta\lambda/\lambda_{0}=0.01$, Fig. 1 depicts the fluctuation-
dissipation relation expressed in Eq. (16). Here,
$\delta\lambda^{2}\langle\partial_{\lambda}\mathcal{H}(0)\rangle_{0}^{2}=2.5\times
10^{-5}$.

Figure 1: Fluctuation-dissipation relation for the linear driven harmonic
oscillator. It was used $\delta\lambda/\lambda_{0}=0.01$. Here,
$\delta\lambda^{2}\langle\partial_{\lambda}\mathcal{H}(0)\rangle_{0}^{2}=2.5\times
10^{-5}$.

##  VI Optimal work fluctuations

It has been shown that for thermally isolated performing weak processes the
optimal excess work is null [12]. Therefore, by the fluctuation-dissipation
relation, the optimal variance of the work for thermally isolated systems
achieves its minimum possible value, given by

$\sigma_{W_{2}}^{2*}=\delta\lambda^{2}\langle\partial_{\lambda}\mathcal{H}(0)\rangle_{0}^{2},$
(19)

which is independent of the rate of the process. It is indeed an intrinsic
characteristic of the system. One may consider it as a quasistatic variance
for the thermally isolated system. This unexpected result shows that although
one achieves by the optimal protocol the quasistatic work for arbitrary rates,
there is always an intrinsic error associated. In particular, it is expected
that $\sigma_{W_{2}}^{2*}(\tau)\propto 1/\beta^{2}$, because of the average on
the canonical ensemble. In this situation, if the system starts at $T\approx
0$, the variance diverges.

Figure 2: Optimal work variance for driven harmonic oscillator. Here,
$\beta^{2}\delta\lambda^{2}\langle\partial_{\lambda}\mathcal{H}(0)\rangle_{0}^{2}=2.5\times
10^{-5}$. It was used $10^{5}$ initial conditions and
$\delta\lambda/\lambda_{0}=0.01$.

To exemplify it, consider again the driven harmonic oscillator, but driven
with the optimal protocol for linear response, given by [8, 12]

$g^{*}(t)=\frac{t}{\tau}+\frac{\delta(t)-\delta(\tau-t)}{4\lambda_{0}\tau}.$
(20)

The optimal work variance is exhibited in Fig. 2 for different rates. In this
particular case,
$\beta^{2}\delta\lambda^{2}\langle\partial_{\lambda}\mathcal{H}(0)\rangle_{0}^{2}=2.5\times
10^{-5}$. Figure 3 depicts the optimal probability distribution function of
the work, which is also non-Gaussian [3] and constant for different rates. I
used in the computational simulation $10^{5}$ initial conditions, and
$\delta\lambda/\lambda_{0}=0.01$.

Figure 3: Optimal work probability density function for driven harmonic
oscillator. Here, $\delta\lambda/\lambda_{0}$=0.01 for $10^{5}$ initial
conditions. The histogram is non-Gaussian ($\mu_{3}>0$) and does not change
with different rates.

##  VII Quantum Ising chain

One important problem to deal with nowadays is the performance of quantum
annealing, aiming to apply in quantum computing [13]. In particular, a
question not so explored is the work fluctuations present in driving
processes. Consider then the quantum Ising model, whose Hamiltonian operator
is

$\mathcal{H}=-J\sum_{i=1}^{N}\sigma_{i}^{x}\sigma_{i+1}^{x}-\Gamma\sum_{i=1}^{N}\sigma_{i}^{z}.$
(21)

where each one of the $N$ spins has a vector
$\vec{\sigma}_{i}:=\sigma_{i}^{x}{\bf x}+\sigma_{i}^{y}{\bf
y}+\sigma_{i}^{z}{\bf z}$ composed by the Pauli matrices. The parameter $J$ is
the coupling energy and $\Gamma$ is the transverse magnetic field. Also, the
system is subjected to periodic boundary conditions to an even number of
spins. In Ref. [12] I have found the optimal protocol that produces a null
excess work of such a system. Under those circumstances, the work fluctuations
will be given by the quasistatic variance of the system. In particular, this
quantity is

$\sigma_{W_{2}}^{2*}=2\delta\Gamma^{2}\sum_{n,m=1}^{N/2}\tanh{\beta\epsilon_{n}}\tanh{\beta\epsilon_{m}},$
(22)

where

$\epsilon_{n}=2\sqrt{J^{2}+\Gamma^{2}-2\Gamma J\cos{(\pi(2n-1)/N)}}.$ (23)

In particular, for purposes of performance of quantum annealing, it is
interesting to observe how the quasistatic variance behaves for a system that
starts with $T=0$. In this case, one has

$\sigma_{W_{2}}^{2*}\propto\delta\Gamma^{2}N^{2}(N+1)^{2}$ (24)

which indicates that the quasistatic variance diverges if the system is in the
thermodynamic limit, where $N\gg 1$. However, in this situation, linear
response only works for very small perturbations [11]. Therefore, after
choosing $\delta\Gamma\propto N^{-2}$, this will compensate the divergence
produced by the thermodynamic limit, generating a finite quasistatic variance
for the system. Knowing how the quasistatic variance of a system behaves could
be an additional criterion to evaluate the validity of linear response in
quantum phase transition situations than only using the criterion proposed in
Ref. [11].

##  VIII Final remarks

In this work, in order to find the optimal work fluctuation for thermally
isolated systems performing weak adiabatic processes, in classical and quantum
realms, for the classical definition of work, the fluctuation-dissipation
relation was extended. The equality presents a breakdown in comparison to the
isothermal case, where an extra quasistatic variance appears, related to the
difference between the quasistatic work and the difference of Helmholtz’s free
energy of the system. From this, the optimal work variance was calculated
showing it achieves its minimum value, independent of the rate of the process.
The result was corroborated by the example of the driven harmonic oscillator.
The optimal variance for the quantum Ising chain is calculated as well,
showing its finiteness if the the linear response validity agreement is
complied. The arbitrary constant for the relaxation function of thermally
isolated systems was shown to be equal to zero to agree with the Second Law of
Thermodynamics.

## References

  * Jarzynski [1997] C. Jarzynski, Phys. Rev. Lett. 78, 2690 (1997).
  * Speck and Seifert [2004] T. Speck and U. Seifert, Physical Review E 70, 066112 (2004).
  * Nazé [2023a] P. Nazé, arXiv preprint arXiv:2304.11965 (2023a).
  * Miller  _et al._ [2019] H. J. D. Miller, M. Scandi, J. Anders, and M. Perarnau-Llobet, Physical Review Letters 123, 230603 (2019).
  * Guarnieri  _et al._ [2023] G. Guarnieri, J. Eisert, and H. J. D. Miller, arXiv preprint arXiv:2307.01885 (2023).
  * Kubo  _et al._ [2012] R. Kubo, M. Toda, and N. Hashitsume,  _Statistical physics II: nonequilibrium statistical mechanics_, Vol. 31 (Springer Science & Business Media, 2012).
  * Nazé and Bonança [2020] P. Nazé and M. V. S. Bonança, Journal of Statistical Mechanics: Theory and Experiment 2020, 013206 (2020).
  * Acconcia and Bonança [2015] T. V. Acconcia and M. V. S. Bonança, Phys. Rev. E 91, 042141 (2015).
  * Bonança [2016] M. V. S. Bonança, Brazilian journal of physics 46, 248 (2016).
  * Myers and Deffner [2021] N. M. Myers and S. Deffner, PRX Quantum 2, 040312 (2021).
  * Nazé  _et al._ [2022] P. Nazé, M. V. S. Bonança, and S. Deffner, Entropy 24, 666 (2022).
  * Nazé [2023b] P. Nazé, arXiv preprint arXiv:2305.17802 (2023b).
  * Deffner and Campbell [2019] S. Deffner and S. Campbell,  _Quantum Thermodynamics: An introduction to the thermodynamics of quantum information_ (Morgan & Claypool Publishers, 2019).