#  Minimal unique palindromic substrings
after single-character substitution***This is a full version of a paper
presented at SPIRE 2021 [14].

Mitsuru Funakoshi  Department of Informatics, Kyushu University.
<EMAIL_ADDRESS>Japan Society for the
Promotion of Science.  Takuya Mieno  Department of Informatics, Kyushu
University<EMAIL_ADDRESS>Japan Society
for the Promotion of Science.

###### Abstract

A _palindrome_ is a string that reads the same forward and backward. A
palindromic substring $w$ of a string $T$ is called a _minimal unique
palindromic substring_ (_MUPS_) of $T$ if $w$ occurs only once in $T$ and any
proper palindromic substring of $w$ occurs at least twice in $T$. MUPSs are
utilized for answering the _shortest unique palindromic substring problem_ ,
which is motivated by molecular biology [Inoue et al., 2018]. Given a string
$T$ of length $n$, all MUPSs of $T$ can be computed in $O(n)$ time. In this
paper, we study the problem of updating the set of MUPSs when a character in
the input string $T$ is substituted by another character. We first analyze the
number $d$ of changes of MUPSs when a character is substituted, and show that
$d$ is in $O(\log n)$. Further, we present an algorithm that uses $O(n)$ time
and space for preprocessing, and updates the set of MUPSs in
$O(\log\sigma+(\log\log n)^{2}+d)$ time where $\sigma$ is the alphabet size.
We also propose a variant of the algorithm, which runs in optimal $O(1+d)$
time when the alphabet size is constant.

##  1 Introduction

Palindromes are strings that read the same forward and backward. Finding
palindromic structures has important applications to analyze biological data
such as DNA, RNA, and proteins, and thus algorithms and combinatorial
properties on palindromic structures have been heavily studied (e.g., see [21,
6, 11, 22, 24, 17, 25] and references therein). In this paper, we treat a
notion of palindromic structures called _minimal unique palindromic substring_
(_MUPS_) that is introduced in [19]. A palindromic substring $T[i..j]$ of a
string $T$ is called a MUPS of $T$ if $T[i..j]$ occurs exactly once in $T$ and
$T[i+1..j-1]$ occurs at least twice in $T$. MUPSs are utilized for solving the
_shortest unique palindromic substring_ (_SUPS_) problem proposed by Inoue et
al. [19], which is motivated by an application in molecular biology. They
showed that there are no more than $n$ MUPSs in any length-$n$ string, and
proposed an $O(n)$-time algorithm to compute all MUPSs of a given string of
length $n$ over an integer alphabet of size $n^{O(1)}$. After that, Watanabe
et al. [28] considered the problem of computing MUPSs in an _run-length
encoded_ (_RLE_) string. They showed that there are no more than $m$ MUPSs in
a string whose RLE size is $m$. Also, they proposed an
$O(m\log\sigma_{R})$-time and $O(m)$-space algorithm to compute all MUPSs of a
string given in RLE, where $\sigma_{R}$ is the number of distinct single-
character runs in the RLE string. Recently, Mieno et al. [23] considered the
problems of computing palindromic structures in the _sliding window_ model.
They showed that the set of MUPSs in a sliding window can be maintained in a
total of $O(n\log\sigma_{W})$ time and $O(D)$ space while a window of size $D$
shifts over a string of length $n$ from the left-end to the right-end, where
$\sigma_{W}$ is the maximum number of distinct characters in the windows. This
result can be rephrased as follows: The set of MUPSs in a string of length $D$
can be updated in amortized $O(\log\sigma_{W})$ time using $O(D)$ space after
deleting the first character or inserting a character to the right-end.

To the best of our knowledge, there is no efficient algorithm for updating the
set of MUPSs after editing a character at _any_ position so far. Now, we
consider the problem of updating the set of MUPSs in a string after
substituting a character at any position. Formally, we tackle the following
problem: Given a string $T$ of length $n$ over an integer alphabet of size
$n^{O(1)}$ to preprocess, and then given a query of single-character
substitution. Afterwards, we return the set of MUPSs of the edited string. In
this paper, we first show that the number $d$ of changes of MUPSs after a
single-character substitution is $O(\log n)$. In addition, we present an
algorithm that uses $O(n)$ time and space for preprocessing, and updates the
set of MUPSs in $O(\log\sigma+(\log\log n)^{2}+d)\subset O(\log n)$ time. We
also propose a variant of the algorithm, which runs in optimal $O(1+d)$ time
when the alphabet size is constant.

#### Related Work.

There are some results for the problem of computing string regularities,
including palindromes, on dynamic strings [5, 2, 3, 9]. In this work, we
consider the problem of computing MUPSs after a single edit operation as a
first step toward a fully dynamic setting. This line of research was initiated
by Amir et al. [4], who tackled the problem of computing the longest common
factor after one edit. After that, other notions of string regularities are
treated in a similar setting [27, 1, 15]. In particular, regarding palindromic
structures, Funakoshi et al. [15] proposed algorithms for computing the
longest palindromic substring after single-character or block-wise edit
operations.

#### Paper Organization.

This paper is organized as follows. Section 2 introduces necessary notations
and algorithmic tools. Section 3 analyzes the changes of the set of MUPSs
after a single-character substitution. We then present an algorithm for
updating the set of MUPSs after a single-character substitution in Section 4.
Finally, we conclude in Section 5.

##  2 Preliminaries

###  2.1 Notations

#### Strings.

Let $\Sigma$ be an _alphabet_ of size $\sigma$. An element of $\Sigma$ is
called a _character_. An element of $\Sigma^{\ast}$ is called a _string_. The
length of a string $T$ is denoted by $|T|$. The _empty string_ $\varepsilon$
is the string of length $0$. For a string $T=xyz$, then $x,y$, and $z$ are
called a _prefix_ , _substring_ , and _suffix_ of $T$, respectively. They are
called a _proper prefix_ , _proper substring_ , _proper suffix_ of $T$ if
$x\neq T$, $y\neq T$, and $z\neq T$, respectively. For each $1\leq i\leq|T|$,
$T[i]$ denotes the $i$-th character of $T$. For each $1\leq i\leq j\leq|T|$,
$T[i..j]$ denotes the substring of $T$ starting at position $i$ and ending at
position $j$. For convenience, let $T[i^{\prime}..j^{\prime}]=\varepsilon$ for
any $i^{\prime}>j^{\prime}$. A positive integer $p$ is said to be a _period_
of a string $T$ if $T[i]=T[i+p]$ for all $1\leq i\leq|T|-p$. For strings $X$
and $Y$, let $\mathit{lcp}(X,Y)$ denotes the length of the _longest common
prefix_ (in short, lcp) of $X$ and $Y$, i.e.,
$\mathit{lcp}(X,Y)=\max\\{\ell\mid X[1..\ell]=Y[1..\ell]\\}$. For a string $T$
and two integers $1\leq i\leq j\leq|T|$, let $\mathit{lce}_{T}(i,j)$ denotes
the length of the _longest common extension_ (in short, lce) of $i$ and $j$ in
$T$, i.e., $\mathit{lce}_{T}(i,j)=\mathit{lcp}(T[i..|T|],T[j..|T|])$. For non-
empty strings $T$ and $w$, $\mathit{beg}_{T}(w)$ denotes the set of beginning
positions of occurrences of $w$ in $T$. Also, for a text position $i$ in $T$,
$\mathit{inbeg}_{T,i}(w)$ denotes the set of beginning positions of
occurrences of $w$ in $T$ where each occurrence covers position $i$. Namely,
$\mathit{beg}_{T}(w)=\\{b\mid T[b..e]=w\\}$ and
$\mathit{inbeg}_{T,i}(w)=\\{b\mid T[b..e]=w\textrm{ and }i\in[b,e]\\}$.
Further, let
$\mathit{xbeg}_{T,i}(w)=\mathit{beg}_{T}(w)\setminus\mathit{inbeg}_{T,i}(w)$.
For convenience,
$|\mathit{beg}_{T}(\varepsilon)|=|\mathit{inbeg}_{T,i}(\varepsilon)|=|\mathit{xbeg}_{T,i}(\varepsilon)|=|T|+1$
for any $T$ and $i$. We say that $w$ is _unique_ in $T$ if
$|\mathit{beg}_{T}(w)|=1$, and that $w$ is _repeating_ in $T$ if
$|\mathit{beg}_{T}(w)|\geq 2$. Note that the empty string is repeating in any
other string. Since every unique substring $u=T[i..j]$ of $T$ occurs exactly
once in $T$, we will sometimes identify $u$ with its corresponding interval
$[i,j]$. In what follows, we consider an arbitrarily fixed string $T$ of
length $n\geq 1$ over an alphabet $\Sigma$ of size $\sigma=n^{O(1)}$.

#### Palindromes.

For a string $w$, $w^{R}$ denotes the reversed string of $w$. A string $w$ is
called a _palindrome_ if $w=w^{R}$. A palindrome $w$ is called an _even-
palindrome_ (resp. _odd-palindrome_) if its length is even (resp. odd). For a
palindrome $w$, its length-$\lfloor|w|/2\rfloor$ prefix (resp.
length-$\lfloor|w|/2\rfloor$ suffix) is called the _left arm_ (resp. _right
arm_) of $w$, and is denoted by $\mathsf{larm}_{w}$ (resp.
$\mathsf{rarm}_{w}$). Also, we call $\mathsf{Larm}_{w}=\mathsf{larm}_{w}\cdot
s_{w}$ (resp. $\mathsf{Rarm}_{w}=s_{w}\cdot\mathsf{rarm}_{w}$) the _extended
left arm_ (resp. _extended right arm_) of $w$ where $s_{w}$ is the character
at the center of $w$ if $w$ is an odd-palindrome, and $s_{w}$ is empty
otherwise. Note that when $w$ is an even-palindrome,
$\mathsf{Rarm}_{w}=\mathsf{rarm}_{w}$ and
$\mathsf{Larm}_{w}=\mathsf{larm}_{w}$. For a non-empty palindromic substring
$w=T[i..j]$ of a string $T$, the center of $w$ is $\frac{i+j}{2}$ and is
denoted by $\mathit{center}(w)$. A non-empty palindromic substring $T[i..j]$
of a string $T$ is said to be _maximal_ if $i=1$, $j=n$, or $T[i-1]\neq
T[j+1]$. For a non-empty palindromic substring $w=T[i..j]$ of a string $T$ and
a non-negative integer $\ell$, $v=T[i-\ell..j+\ell]$ is said to be an
_expansion_ of $w$ if $1\leq i-\ell\leq j+\ell\leq n$ and $v$ is a palindrome.
Also, $T[i+\ell..j-\ell]$ is said to be a _contraction_ of $w$. Now we show
periodic properties of palindromic suffixes of $T[1..i]$. Let
$\mathbf{S}_{i}=\\{s_{1},\ldots,s_{g}\\}$ be the set of lengths of palindromic
suffixes of $T[1..i]$, where $g$ is the number of palindromic suffixes of
$T[1..i]$ and $s_{k-1}\leq s_{k}$ for $2\leq k\leq g$. Let $p_{k}$ be the
progression difference for $s_{k}$, i.e., $p_{k}=s_{k}-s_{k-1}$ for $2\leq
k\leq g$. For convenience, let $p_{1}=1$.

Then, the following results are known:

######  Lemma 1 ([6, 16, 22]).

  1. (A)

For any $1\leq k<g$, $p_{k+1}\geq p_{k}$.

  2. (B)

For any $1<k<g$, if $p_{k+1}\neq p_{k}$, then $p_{k+1}\geq p_{k}+p_{k-1}$.

  3. (C)

$\mathbf{S}_{i}$ can be represented by $O(\log i)$ arithmetic progressions,
where each arithmetic progression is a tuple $\langle a,p,f\rangle$
representing the sequence $a,a+p,\ldots,a+(f-1)p$ of lengths of $f$
palindromic suffixes with common difference $p$.

  4. (D)

The common difference $p$ is a smallest period of every palindromic suffixes
of $T[1..i]$ whose length belongs to the arithmetic progression $\langle
a,p,f\rangle$.

For each $1\leq j\leq f$, we will use the convention that $a(j)=a+(j-1)p$,
namely $a(j)$ denotes the $j$-th shortest element for $\langle a,p,f\rangle$.
For simplicity, let $Y=T[1..i]$ and $Z=T[i+1..n]$. Let $\mathit{lcp}(x,y)$ for
strings $x$ and $y$ denote the length of the longest common prefix of $x$ and
$y$. Also, let $\mathit{Ext}(a(j))$ denote the length of the maximal
palindrome that is obtained by extending $a(j)$ in $YZ$.

######  Lemma 2 ([22]).

For any $\langle a,p,f\rangle$ of palndromic suffixes of $T[1..i]$, there
exist palindromes $u,v$ and a non-negative integer $q$, such that
$(uv)^{f+q-1}u$ (resp. $(uv)^{q}u$) is the longest (resp. shortest)
palindromic suffixes represented by $\langle a,p,f\rangle$ with $|uv|=p$. Let
$\alpha=\mathit{lcp}((Y[1..|Y|-a(1)])^{R},Z)$ and
$\beta=\mathit{lcp}((Y[1..|Y|-a(f)])^{R},Z)$. Then
$\mathit{Ext}(a(j))=a(j)+2\min\\{\alpha,\beta+(f-j)p\\}$. Further, if there
exists $a(h)\in\langle a,p,f\rangle$ such that $a(h)+\alpha=a(f)+\beta$, then
$\mathit{Ext}(a(h))=a(h)+2\mathit{lcp}((Y[1..|Y|-a(h)])^{R},Z)\geq\mathit{Ext}(a(j))$
for any $j\neq h$.

By Lemmas 1 and 2, we obtain the following corollary:

######  Corollary 1.

For a position $i$, divide the set of palindromic suffixes of $T[1..i]$ into
groups $G_{1},G_{2},\ldots,G_{m_{i}}$ w.r.t their smallest periods. Then,
$m_{i}\in O(\log i)$ holds. Also, for each group $G_{k}$, the following
properties hold:

  1. (1)

The difference between centers of any two palindromes in $G_{k}$ is an integer
power of $0.5p_{k}$, where $p_{k}$ is their smallest period.

  2. (2)

For all maximal palindromes $e_{1},\ldots,e_{t}$ in $T$ that are expansions of
palindromes in $G_{k}$, excluding at most one, their smallest period is also
$p_{k}$.

  3. (3)

Among $e_{1},\ldots,e_{t}$, any palindrome is contained by the longest one or
the second longest one.

We remark that symmetric arguments hold for palindromic prefixes as well.

A non-empty string $w$ is called a _1-mismatch palindrome_ if there is exactly
one mismatched position between $w[1..\lfloor|w|/2\rfloor]$ and
$w[\lceil|w|/2\rceil+1..|w|]^{R}$. Informally, a 1-mismatch palindrome is a
pseudo palindrome with a mismatch position between their arms. As in the case
of palindromes, a 1-mismatch palindromic substring $T[i..j]$ of a string $T$
is said to be _maximal_ if $i=1$, $j=n$ or $T[i-1]\neq T[j+1]$.

A palindromic substring $T[i..j]$ of a string $T$ is called a _minimal unique
palindromic substring_ (_MUPS_) of $T$ if $T[i..j]$ is unique in $T$ and
$T[i+1..j-1]$ is repeating in $T$. We denote by $\mathsf{MUPS}(T)$ the set of
intervals corresponding to MUPSs of a string $T$. A MUPS cannot be a substring
of another palindrome with a different center. Also, it is known that the
number of MUPSs of $T$ is at most $n$, and set $\mathsf{MUPS}(T)$ can be
computed in $O(n)$ time for a given string $T$ over an integer alphabet [19].
The following lemma states that the total sum of occurrences of strings which
are extended arms of MUPSs is $O(n)$:

######  Lemma 3.

The total sum of occurrences of the extended right arms of all MUPSs in a
string $T$ is at most $2n$. Similarly, the total sum of occurrences of the
extended left arms of all MUPSs in $T$ is at most $2n$.

###### Proof..

It suffices to prove the former statement for the extended _right_ arms since
the latter can be proved symmetrically. Let $w_{1}$ and $w_{2}$ be distinct
odd-length MUPSs of $T$ with $|w_{1}|\leq|w_{2}|$. For the sake of
contradiction, we assume that
$T[j..j+|\mathsf{Rarm}_{w_{1}}|-1]=\mathsf{Rarm}_{w_{1}}$ and
$T[j..j+|\mathsf{Rarm}_{w_{2}}|-1]=\mathsf{Rarm}_{w_{2}}$ for some position
$j$ in $T$. Namely, $\mathsf{Rarm}_{w_{1}}$ is a prefix of
$\mathsf{Rarm}_{w_{2}}$. Then, $\mathsf{larm}_{w_{1}}$ is a suffix of
$\mathsf{larm}_{w_{2}}$ by palindromic symmetry. This means that $w_{1}$ is a
substring of $w_{2}$. This contradicts that $w_{2}$ is a MUPS of $T$. Thus,
all occurrences of the extended right arms of all odd-length MUPSs are
different, i.e., the total number of the occurrences is at most $n$.
Similarly, the total number of all occurrences of the right arms of all even-
length MUPSs is also at most $n$. ∎

###  2.2 Tools

This subsection lists some data structures used in our algorithm. Our model of
computation is a standard word RAM model with machine word size $\Omega(\log
n)$.

#### Suffix Trees.

The _suffix tree_ of $T$ is the compacted trie for all suffixes of $T$ [29].
We denote by $\mathsf{STree}(T)$ the suffix tree of $T$. If a given string $T$
is over an integer alphabet of size $n^{O(1)}$, $\mathsf{STree}(T)$ can be
constructed in $O(n)$ time [12]. Not all substrings of $T$ correspond to nodes
in $\mathsf{STree}(T)$. However, the loci of such substrings can be made
explicit in linear time:

######  Lemma 4 (Corollary 8.1 in [20]).

Given $m$ substrings of $T$, represented by intervals in $T$, we can compute
the locus of each substring in $\mathsf{STree}(T)$ in $O(n+m)$ total time.
Moreover, the loci of all the substrings in $\mathsf{STree}(T)$ can be made
explicit in $O(n+m)$ extra time.

Also, this lemma implies the following corollary:

######  Corollary 2.

Given $m$ substrings of $T$, represented by intervals in $T$, we can sort them
in $O(n+m)$ time.

#### LCE Queries.

An _LCE query_ on a string $T$ is, given two indices $i,j$ of $T$, to compute
$\mathit{lce}_{T}(i,j)$. Using $\mathsf{STree}(T\$)$ enhanced with a lowest
common ancestor data structure, we can answer any LCE query on $T$ in constant
time where $\$$ is a special character with $\$\not\in\Sigma$. In the same
way, we can compute the lcp value between any two suffixes of $T$ or $T^{R}$
in constant time by using $\mathsf{STree}(T\$T^{R}\\#)$ where $\\#$ is another
special character with $\\#\not\in\Sigma$.

#### NCA Queries.

A _nearest colored ancestor query_ (NCA query) on a tree $\mathcal{T}$ with
_colored_ nodes is, given a query node $v$ and a color $C$, to compute the
nearest ancestor $u$ of $v$ such that the color of $u$ is $C$. Noticing that
the notion of NCA is a generalization of well-known _nearest marked ancestor_.
For NCA queries, we will use the following known results:

######  Lemma 5 ([18]).

Given a tree $\mathcal{T}$ with colored nodes, a data structure of size $O(N)$
can be constructed in deterministic $O(N\log\log N)$ time or expected $O(N)$
time to answer any NCA query in $O(\log\log N)$ time, where $N$ is the number
of nodes of $\mathcal{T}$.

######  Lemma 6 ([8, 10]).

If the number of colors is $O(\log N)$, a data structure of size $O(N)$ can be
constructed in $O(N)$ time to answer any NCA query in $O(1)$ time.

#### Eertrees.

The _eertree_ (a.k.a. palindromic tree) of $T$ is a pair of rooted edge-
labeled trees $\mathcal{T}_{\mathsf{odd}}$ and $\mathcal{T}_{\mathsf{even}}$
representing all distinct palindromes in $T$ [24]. The roots of
$\mathcal{T}_{\mathsf{odd}}$ and $\mathcal{T}_{\mathsf{even}}$ represent
$\varepsilon$. Each non-root node of $\mathcal{T}_{\mathsf{odd}}$ (resp.
$\mathcal{T}_{\mathsf{even}}$) represents an odd-palindrome (resp. even-
palindrome) which occurs in $T$. Let $\mathit{pal}(v)$ be the palindrome
represented by a node $v$. For the root $r_{\mathsf{odd}}$ of
$\mathcal{T}_{\mathsf{odd}}$, there is an edge $(r_{\mathsf{odd}},u)$ labeled
by $a\in\Sigma$ if there is a node $u$ with $\mathit{pal}(u)=a$. For any node
$v$ in the eertree except for $r_{\mathsf{odd}}$, there is an edge $(v,w)$
labeled by $a\in\Sigma$ if there is a node $w$ with
$\mathit{pal}(w)=a\cdot\mathit{pal}(v)\cdot a$. We denote by
$\mathsf{EERTREE}(T)$ the eertree of $T$. We will sometimes identify a node
$u$ in $\mathsf{EERTREE}(T)$ with its corresponding palindrome
$\mathit{pal}(u)$. Also, the path from a node $u$ to a node $v$ in
$\mathsf{EERTREE}(T)$ is denoted by
$\mathit{pal}(u)\rightsquigarrow\mathit{pal}(v)$. If a given string $T$ is
over an integer alphabet of size $n^{O(1)}$, $\mathsf{EERTREE}(T)$ can be
constructed in $O(n)$ time [24].

#### Path-Tree LCE Queries.

A _path-tree LCE query_ is a generalized LCE query on a rooted edge-labeled
tree $\mathcal{T}$ [7]: Given three nodes $u$, $v$, and $w$ in $\mathcal{T}$
where $u$ is an ancestor of $v$, to compute the lcp between the path-string
from $u$ to $v$ and any path-string from $w$ to a descendant leaf. The
following result is known:

######  Theorem 1 (Theorem 2 of [7]).

For a tree $\mathcal{T}$ with $N$ nodes, a data structure of size $O(N)$ can
be constructed in $O(N)$ time to answer any path–tree LCE query in
$O((\log\log N)^{2})$ time.

We will use later path-tree LCE queries on the eertree of the input string.

#### Stabbing Queries.

Let $\mathcal{I}$ be a set of $n$ intervals, each of which is a subinterval of
the universe $U=[1,O(n)]$. An _interval stabbing query_ on $\mathcal{I}$ is,
given a query point $q\in U$, to report all intervals $I\in\mathcal{I}$ such
that $I$ is _stabbed_ by $q$, i.e., $q\in I$. We can answer such a query in
$O(1+k)$ time after $O(n)$-time preprocessing, where $k$ is the number of
intervals to report [26].

##  3 Changes of MUPSs After Single Character Substitution

In the following, we fix the original string $T$ of length $n$, the text
position $i$ in $T$ to be substituted, and the string $T^{\prime}$ after the
substitution. Namely, $T[i]\neq T^{\prime}[i]$ and $T[j]=T^{\prime}[j]$ for
each $j$ with $1\leq j\leq n$ and $j\neq i$. This section analyzes the changes
of the set of MUPSs when $T[i]$ is substituted by $T^{\prime}[i]$. For
palindromes covering editing position $i$, Lemma 7 holds.

######  Lemma 7.

For a palindrome $w$, if $\mathit{inbeg}_{T,i}(w)\neq\emptyset$, then
$\mathit{inbeg}_{T^{\prime},i}(w)=\emptyset$.

###### Proof..

For the sake of contradiction, we assume that there is a palindrome $w$ with
$\mathit{inbeg}_{T,i}(w)\neq\emptyset$ and
$\mathit{inbeg}_{T^{\prime},i}(w)\neq\emptyset$. Let $c$ (resp. $c^{\prime}$)
be the center of an occurrence of $w$ in $T$ (resp. in $T^{\prime}$) covering
position $i$. It is clear that $c\neq c^{\prime}$ since $T[i]$ is substituted
by another character $T^{\prime}[i]$. Also, it suffices to consider when
$c<c^{\prime}$ from the symmetry of $T$ and $T^{\prime}$. Let $d$ (resp.
$d^{\prime}$) be the distance between $c$ and $i$ (resp. $c^{\prime}$ and
$i$), i.e., $d=|i-c|$ and $d^{\prime}=|i-c^{\prime}|$.

There are the following two cases: either (1) $i\not\in[c,c^{\prime}]$ or (2)
$i\in[c,c^{\prime}]$. See also Fig. 1 for illustration. (1) Now we consider
the case when $c^{\prime}<i$. Another case ($i<c$) can be treated similarly.
On the one hand, since $c$ and $c^{\prime}$ are the centers of $w$,
$T^{\prime}[c^{\prime}+d]=T[c+d]=T[i]$. Further,
$T^{\prime}[c^{\prime}-d]=T[c^{\prime}+d]$ by palindromic symmetry, and hence,
$T^{\prime}[c^{\prime}-d]=T[i]$. On the other hand, again, since $c$ and
$c^{\prime}$ are the centers of $w$,
$T[c-d^{\prime}]=T^{\prime}[c^{\prime}-d^{\prime}]$. Further,
$T^{\prime}[c^{\prime}-d^{\prime}]=T^{\prime}[c^{\prime}+d^{\prime}]=T^{\prime}[i]$
by palindromic symmetry, and hence, $T[c-d^{\prime}]=T^{\prime}[i]$. Also,
$T^{\prime}[c-d^{\prime}]=T[c-d^{\prime}]=T^{\prime}[i]$ since
$c-d^{\prime}\neq i$. Since $c^{\prime}-d=c-d^{\prime}$ holds in this case,
$T[i]=T^{\prime}[c^{\prime}-d]=T^{\prime}[c-d^{\prime}]=T^{\prime}[i]$, a
contradiction.

(2) Similar to the first case, it can be seen that
$T^{\prime}[c^{\prime}-d]=T[c-d]=T[i]$. If $d=d^{\prime}$, then
$T[i]=T^{\prime}[c^{\prime}-d]=T^{\prime}[c^{\prime}-d^{\prime}]=T^{\prime}[i]$,
a contradiction. Hence $d\neq d^{\prime}$ holds, and thus,
$T^{\prime}[c+d^{\prime}]=T[c+d^{\prime}]$. Also,
$T[c+d^{\prime}]=T^{\prime}[c^{\prime}+d^{\prime}]=T^{\prime}[c^{\prime}-d^{\prime}]=T^{\prime}[i]$
holds. Finally, since $c^{\prime}-d=c+d^{\prime}$ holds in this case,
$T[i]=T^{\prime}[c^{\prime}-d]=T^{\prime}[c+d^{\prime}]=T^{\prime}[i]$, a
contradiction. ∎

Figure 1: Illustration for the two cases of Lemma 7. Note that this
illustration is for the sake of contradiction.

For a position $i$, let $\mathcal{W}_{i}$ be the set of palindromes $w$ such
that $|\mathit{inbeg}_{T,i}(w)|\geq 1$, $|\mathit{xbeg}_{T,i}(w)|=1$, and $w$
is minimal, i.e., $|\mathit{inbeg}_{T,i}(v)|=0$ or
$|\mathit{xbeg}_{T,i}(v)|\geq 2$ where $v=w[2..|w|-1]$. This set
$\mathcal{W}_{i}$ is useful for analyzing the number of changes of MUPSs in
the proof of Theorem 2.

######  Lemma 8.

For any position $i$ in $T$, $|\mathcal{W}_{i}|\in O(\log n)$.

###### Proof..

First, by minimality of palindromes in $\mathcal{W}_{i}$, centers of
palindromes in $\mathcal{W}_{i}$ are different from each other. Let
$\mathcal{W}_{i}^{L}\subset\mathcal{W}_{i}$ (resp.
$\mathcal{W}_{i}^{R}\subset\mathcal{W}_{i}$) be the set of palindromes in
$\mathcal{W}_{i}$ whose center is at most $i$ (resp. at least $i$).

Let us consider the size of $\mathcal{W}_{i}^{L}$. Every palindrome in
$\mathcal{W}_{i}^{L}$ is an expansion of some palindromic suffix of $T[1..i]$.
From Corollary 1, the set of palindromic suffixes of $T[1..i]$ can be divided
into $m_{i}\in O(\log i)$ groups w.r.t. their smallest period. Let
$G_{1},G_{2},\ldots,G_{m_{i}}$ be such groups for palindromic suffixes of
$T[1..i]$, and let $p_{k}$ be the smallest period corresponding to $G_{k}$.
Also, for each $k$ with $1\leq k\leq m_{i}$, let $E_{k}$ be the union set of
all expansions of every palindrome in $G_{k}$. Let
$H_{k}=\mathcal{W}_{i}^{L}\cap E_{k}$. Since
$|\mathcal{W}_{i}^{L}|=|\bigcup_{k=1}^{m_{i}}H_{k}|=\sum_{k=1}^{m_{i}}|H_{k}|$
and $m_{i}\in O(\log n)$, it suffices to show that $|H_{k}|$ is at most a
constant.

For the sake of contradiction, we assume $|H_{k}|\geq 4$. From (2) of
Corollary 1, at least three palindromes in $H_{k}$ has the same smallest
period $p_{k}$. Also, by (1) of Corollary 1, the difference between centers of
any two palindromes in $H_{k}$ is a power of $0.5p_{k}$. Therefore, at least
two distinct palindromes in $H_{k}$ have a difference of power of $p_{k}$ in
their center positions. Let $w_{1}$, $w_{2}$ be such palindromes, and assume
that $|w_{1}|\leq|w_{2}|$ w.l.o.g.. Then, the string between the centers of
$w_{1}$ and $w_{2}$ can be represented by $x^{j}$ for positive integer $j$ and
string $x$ of length $p_{k}$. Since the smallest period of $w_{1}$ is $p_{k}$,
its extended right arm $\mathsf{Rarm}_{w_{1}}$ can be written by
$\mathsf{Rarm}_{w_{1}}=x^{j_{1}}x^{\prime}_{1}$ where $j_{1}$ is a non-
negative integer and $x^{\prime}_{1}$ is a proper prefix of $x$. Similarly,
the extended right arm $\mathsf{Rarm}_{w_{2}}$ of $w_{2}$ can be written by
$\mathsf{Rarm}_{w_{2}}=x^{j_{2}}x^{\prime}_{2}$ where $j_{2}$ is a non-
negative integer and $x^{\prime}_{2}$ is a proper prefix of $x$. See also Fig.
2 for illustration. If $|w_{1}|=|w_{2}|$, then this leads $j_{1}=j_{2}$ and
$x^{\prime}_{1}=x^{\prime}_{2}$, i.e., $w_{1}=w_{2}$, a contradiction. If
$|w_{1}|<|w_{2}|$, then $j_{1}<j_{2}$ or $j_{1}=j_{2}$ and
$|x^{\prime}_{1}|<|x^{\prime}_{2}|$. In both cases, $\mathsf{Rarm}_{w_{1}}$ is
a proper prefix of $\mathsf{Rarm}_{w_{2}}$, i.e, $w_{1}$ is a contraction of
$w_{2}$. This contradicts the minimality of $w_{2}$. Thus $|H_{k}|\leq 3$
holds, and hence, we obtain
$|\mathcal{W}_{i}^{L}|=\sum_{k=1}^{m_{i}}|H_{k}|\leq 3m_{i}\in O(\log n)$.

Similarly, the size of $\mathcal{W}_{i}^{R}$ is also $O(\log n)$. Therefore,
$|\mathcal{W}_{i}|\in O(\log n)$. ∎

Figure 2: Example for Lemma 8, where $w_{1}$ and $w_{2}$ have the same
smallest period $5$ and the difference between centers of them is a power of
$5$. Here $x=\mathtt{aabaa}$, $x^{\prime}_{1}=\mathtt{aaba}$, and
$x^{\prime}_{2}=\mathtt{aab}$.

######  Lemma 9.

For each position $i$ in $T$, the number of MUPSs covering $i$ is $O(\log n)$.

###### Proof..

By symmetry, it suffices to show that the number of MUPSs covering $i$ and
centered _before_ $i$ is $O(\log n)$. Each of such MUPSs is an expansion of
some palindromic suffix of $T[1..i]$. Thus, similar to the proof of Lemma 8,
we consider dividing the set of palindromic suffixes of $T[1..i]$ into
$m_{i}\in O(\log i)$ groups, $G_{1},G_{2},\ldots,G_{m_{i}}$ w.r.t. their
smallest periods. In the following, we consider MUPSs that are expansions of
palindromes in an arbitrary group $G_{k}$. We show that the number of such
MUPSs is at most two by contradiction. We assume the contrary, i.e., there are
three MUPSs that are expansions of palindromes in $G_{k}$. By (3) of Corollary
1, at least one of the three MUPSs is a substring of an expansion of a
palindrome in $G_{k}$ with a different center. This contradicts that a MUPS
cannot be a substring of another palindrome with a different center. Thus, the
number of MUPSs that are expansions of palindromes in $G_{k}$ is at most two,
and we finish the proof. ∎

By using Lemmas 7, 8, and 9, we show the following theorem:

######  Theorem 2.

$|\mathsf{MUPS}(T)\bigtriangleup\mathsf{MUPS}(T^{\prime})|\in O(\log n)$
always holds.

###### Proof..

In the following, we consider the number of MUPSs to be removed.

First, at most one interval can be a MUPS of $T$ centered at $i$. Also, any
other interval in $\mathsf{MUPS}(T)$ covering position $i$ cannot be an
element of $\mathsf{MUPS}(T^{\prime})$ since its corresponding string in
$T^{\prime}$ is no longer a palindrome. By Lemma 9, the number of such MUPSs
is $O(\log n)$.

Next, let us consider MUPSs not covering position $i$. When a MUPS $w$ of $T$
not covering $i$ is no longer a MUPS of $T^{\prime}$, then either (A) $w$ is
repeating in $T^{\prime}$ or (B) $w$ is unique in $T^{\prime}$ but is not
minimal.

Let $w_{1}$ be a MUPS of the case (A). Since $w_{1}$ does not cover $i$, is
unique in $T$, and is repeating in $T^{\prime}$,
$|\mathit{inbeg}_{T^{\prime},i}(w_{1})|\geq 1$ and
$|\mathit{xbeg}_{T^{\prime},i}(w_{1})|=1$. Let $v_{1}$ be the minimal
contraction of $w_{1}$ such that $|\mathit{inbeg}_{T^{\prime},i}(v_{1})|\geq
1$ and $|\mathit{xbeg}_{T^{\prime},i}(v_{1})|=1$. Contrary, $w_{1}$ is the
only MUPS of the case (A) which is an expansion of $v_{1}$ since
$|\mathit{xbeg}_{T^{\prime},i}(v_{1})|=1$. Namely, there is a one-to-one
relation between $w_{1}$ and $v_{1}$. By Lemma 8, the number of palindromes
that satisfy the above conditions of $v_{1}$ is $O(\log n)$. Thus, the number
of MUPSs of the case (A) is also $O(\log n)$.

Let $w_{2}$ be a MUPS of the case (B). In $T^{\prime}$, $w_{2}$ covers some
MUPS as a proper substring since it is not a MUPS and is unique in
$T^{\prime}$. Let $v_{2}$ be the MUPS of $T^{\prime}$, which is a proper
substring of $w_{2}$. While $v_{2}$ is unique in $T^{\prime}$, it is repeating
in $T$ since $w_{2}$ is a MUPS of $T$. Namely,
$|\mathit{inbeg}_{T,i}(v_{2})|\geq 1$ and $|\mathit{xbeg}_{T,i}(v_{2})|=1$
hold. Also, $v_{2}$ is actually minimal: Let $u_{2}=v_{2}[2..|v_{2}|-1]$. If
we assume that $|\mathit{inbeg}_{T,i}(u_{2})|\geq 1$ and
$|\mathit{xbeg}_{T,i}(u_{2})|=1$, then $u_{2}$ becomes unique in $T^{\prime}$,
and this contradicts that $v_{2}$ is a MUPS of $T^{\prime}$. Furthermore,
similar to the above discussions, there is a one-to-one relation between
$w_{2}$ and $v_{2}$. Again by Lemma 8, the number of palindromes that satisfy
the above conditions of $v_{2}$ is $O(\log n)$. Thus, the number of MUPSs of
the case (B) is also $O(\log n)$.

Therefore, $|\mathsf{MUPS}(T)\setminus\mathsf{MUPS}(T^{\prime})|\in O(\log n)$
holds. Also, $|\mathsf{MUPS}(T^{\prime})\setminus\mathsf{MUPS}(T)|\in O(\log
n)$ holds by symmetry.

To summarize,
$|\mathsf{MUPS}(T)\bigtriangleup\mathsf{MUPS}(T^{\prime})|=|\mathsf{MUPS}(T)\setminus\mathsf{MUPS}(T^{\prime})\cup\mathsf{MUPS}(T^{\prime})\setminus\mathsf{MUPS}(T)|=|\mathsf{MUPS}(T)\setminus\mathsf{MUPS}(T^{\prime})|+|\mathsf{MUPS}(T^{\prime})\setminus\mathsf{MUPS}(T)|\in
O(\log n)$. ∎

##  4 Algorithms for Updating Set of MUPSs

In this section, we propose an algorithm for updating the set of MUPSs when a
single-character in the original string is substituted by another character.
We denote by $\mathit{sub}(i,s)$ the substitution query, that is, to
substitute $T[i]$ by another character $s$. First, we define a sub-problem
that will be used in our algorithm:

######  Problem 1.

Given a substitution query $\mathit{sub}(i,s)$ on $T$, compute the longest
odd-palindromic substring $v$ of $T^{\prime}$ such that $\mathit{center}(v)=i$
and $v$ occurs in $T$ if it exists. Also, if such $v$ exists, determine
whether $v$ is unique in $T$ or not. Furthermore, if $v$ is unique in $T$,
compute the contraction of $v$ that is a MUPS of $T$.

We show the following lemma:

######  Lemma 10.

After $O(n)$-time preprocessing, we can answer Problem 1 in
$O(\delta(n,\sigma)+(\log\log n)^{2})$ time where $\delta(n,\sigma)$ denote
the time to retrieve any child of the root of the odd-tree of
$\mathsf{EERTREE}(T)$.

###### Proof..

In the preprocessing, we construct $\mathsf{EERTREE}(T)$ and apply the
preprocessing for the path-tree LCE queries to the odd-tree
$\mathcal{T}_{\mathsf{odd}}$ of $\mathsf{EERTREE}(T)$. Also, we mark the nodes
in $\mathsf{EERTREE}(T)$ that correspond to MUPSs of $T$ and apply the
preprocessing for the nearest marked ancestor (NMA) queries. The preprocessing
time is $O(n)$.

Given a query $\mathit{sub}(i,s)$, we query the path-tree LCE between path
$T[i]\rightsquigarrow\mathsf{larm}_{w}T[i]\mathsf{rarm}_{w}$ and tree rooted
at $s$ on $\mathcal{T}_{\mathsf{odd}}$ where $w$ is the maximal palindrome in
$T^{\prime}$ centered at $i$. Let $\ell_{w}$ be the depth of the LCE nodes.
Then the contraction $v$ of $w$ with $|\mathsf{Rarm}_{v}|=\ell_{w}$ occurs in
$T$. Also, $v$ is the longest since any other contraction $u$ of $w$ longer
than $v$ does not occur in $T$. Further, we can determine whether $v$ is
unique in $T$ or not by checking the existence of a mark on path
$s\rightsquigarrow v$. It can be done by querying NMA, and the MUPS of $T$
contained in $v$ can be computed simultaneously, if $v$ is unique in $T$.

We can compute the value $\ell_{w}$ in $\delta(n,\sigma)$ time for searching
for the node $s$ in $\mathcal{T}_{\mathsf{odd}}$, plus $O((\log\log n)^{2})$
time for the path-tree LCE query. ∎

When $\sigma\in O(n)$, we can easily achieve $\delta(n,\sigma)\in O(1)$ with
linear space, by using an array of size $\sigma$. Otherwise, we achieve
$\delta(n,\sigma)\in O(\log\sigma)$ for a general ordered alphabet by using a
binary search tree.

In the rest of this paper, we propose an algorithm to compute the changes in
MUPSs after a single-character substitution. We compute MUPSs to be removed
and added separately. We show how to compute all MUPSs to be removed in
Section 4.1. Also, we show how to compute all MUPSs to be added in Section
4.2. In Section 4.3, we introduce another solution for Problem 1. Our strategy
is basically to pre-compute changes in MUPSs for some queries as much as
possible within linear time. The other changes will be detected on the fly by
using some data structures.

###  4.1 Computing MUPSs to be Removed

We categorize MUPSs to be removed into three types as follows:

R1)

A MUPS of $T$ that covers $i$.

R2)

A MUPS of $T$ that does not cover $i$ and is repeating in $T^{\prime}$.

R3)

A MUPS of $T$ that does not cover $i$ and is unique but not minimal in
$T^{\prime}$.

See Fig. 3 for illustration.

Figure 3:  Illustration for three types of MUPSs to be removed. The red arrows
represent MUPSs. $w_{1}$, $w_{2}$, and $w_{3}$ are MUPSs of Type R1, Type R2,
and Type R3 in $T$, respectively. Also, $v$ is the MUPS of $T^{\prime}$ that
is a contraction of $w_{3}$. It is not unique in $T$, but is unique in
$T^{\prime}$.

In the following, we describe how to compute all MUPSs for each type
separately.

#### Type R1.

All MUPSs covering editing position $i$ are always removed. Thus, we can
detect them in $O(1+\alpha_{\mathit{rem}})$ time after a simple linear time
preprocessing (e.g., using stabbing queries), where $\alpha_{\mathit{rem}}$ is
the number of MUPSs of Type R1.

#### Type R2.

Before describing our algorithm, we give a few observations about MUPSs of
Type R2. Let $w$ be a MUPS of Type R2. Since $w$ is unique in $T$ and is
repeating in $T^{\prime}$, $|\mathit{inbeg}_{T^{\prime},i}(w)|\geq 1$. When
$w$ occurs in $T^{\prime}$ centered at editing position $i$, we retrieve such
$w$ by applying Problem 1. If it is not the case, we can utilize the following
observations: Consider the starting position $j$ of an occurrence of $w$ in
$T^{\prime}$ such that $T^{\prime}[j..j+|w|-1]=w$ and $i\in[j,j+|w|-1]$. If
position $i$ is covered in the right arm of $T^{\prime}[j..j+|w|-1]$, then
$\mathsf{Larm}_{w}$ occurs at position $j$ in both $T$ and $T^{\prime}$.
Further, the Hamming distance between $T[j+|\mathsf{Larm}_{w}|..j+|w|-1]$ and
$w[|\mathsf{Larm}_{w}|+1..|w|]=\mathsf{rarm}_{w}$ equals $1$. Namely, for each
occurrence at position $k$ of string $\mathsf{Larm}_{w}$ in $T$, $w$ can occur
at $k$ in $T^{\prime}$ only if the Hamming distance between
$T[k+|\mathsf{Larm}_{w}|..k+|w|-1]$ and $w[|\mathsf{Larm}_{w}|+1..|w|]$ equals
$1$. In other words, if the Hamming distance is greater than $1$, $w$ cannot
occur at $k$ in $T^{\prime}$. See also Fig. 4.

Figure 4: Example for observations about Type R2, where
$T=\mathtt{aabaacaabacaabbaaabcbc}$ and $w=\mathtt{aabaa}$.
$\mathsf{Larm}_{w}=\mathtt{aab}$ occurs at position $7$, $12$, and $17$
excluding the occurrence of $w$. Since the Hamming distance between
$T[10..11]$ and $w[4..5]$ equals 1, $w$ occurs at position $7$ when $T[11]$ is
substituted by $\mathtt{a}$. Also, $w$ occurs at position $12$ when $T[15]$ is
substituted by $\mathtt{a}$. Conversely, $w$ cannot occur at $17$ after any
single-character substitution since the Hamming distance between $T[20..21]$
and $w[4..5]$ equals 2.

The strategy of the algorithm for MUPSs of Type R2 is following: A MUPS of
Type R2 having occurrence centered at editing position $i$ in $T^{\prime}$ is
found by applying Problem 1. For the remaining MUPSs of Type R2, we precompute
them by using the above observations.

##### Preprocessing.

In the preprocessing phase, we first apply the $O(n)$-time preprocessing of
Lemma 10 for Problem 1. Next, we initialize the set
$\mathcal{A}_{R2}=\emptyset$. The set $\mathcal{A}_{R2}$ will become an
_index_ of MUPSs of Type R2 when the preprocessing is finished. For each MUPS
$w=T[b..e]$ of $T$, we process the followings: For the beginning position
$j\neq b$ of each occurrence of $\mathsf{Larm}_{w}$ in $T$, we first compute
the lcp value between $T[j+|\mathsf{Larm}_{w}|..|T|]\$$ and
$\mathsf{rarm}_{w}$ with allowing one mismatch. Note that
$T[j+|\mathsf{Larm}_{w}|..|T|]\$$ must have at least one mismatch with
$\mathsf{rarm}_{w}$, since $T[j..j+|\mathsf{Larm}_{w}|-1]=\mathsf{Larm}_{w}$,
$j\neq b$, and $T[b..e]$ is unique in $T$. If there are two mismatch positions
between them, do nothing for this occurrence since $w$ cannot occur at $j$
after any substitution. We can check this by querying LCE at most twice.
Otherwise, let $q=j+|\mathsf{Larm}_{w}|-1+d$ be the mismatched position in
$T$. When the $q$-th character of $T$ is substituted by the character
$\mathsf{rarm}_{w}[d]$, $w=T[b..e]$ occurs at $j\neq b$, i.e., it is a MUPS of
Type R2. So we add MUPS $w=T[b..e]$ into $\mathcal{A}_{R2}$ with the pair of
index and character $(q,\mathsf{rarm}_{w}[d])$ as the key. In addition,
symmetrically, we update $\mathcal{A}_{R2}$ for each occurrence of
$\mathsf{Rarm}_{w}$ in $T$. After finishing the above processes for every MUPS
of $T$, we sort the elements of $\mathcal{A}_{R2}$ by radix sort on the keys.
If there are multiple identical elements with the same key, we unify them into
a single element. Also, if there are multiple elements with the same key, we
store them in a linear list. By Lemma 3, the total number of occurrences of
arms of MUPSs is $O(n)$, and hence, the total preprocessing time is $O(n)$.

##### Query.

Given a query $\mathit{sub}(i,s)$, we query Problem 1 with the same pair
$(i,s)$ as the input. Then, we complete checking whether there exists a MUPS
of Type R2 centered at $i$. Next, consider the existence of the remaining
MUPSs of Type R2. First, an element in $\mathcal{A}_{R2}$ corresponding to the
key $(i,s)$ can be detected in $O(\log\sigma_{i})$ time by using random access
on indices and binary search on characters, where $\sigma_{i}$ is the number
of characters $s_{i}$ such that the key $(i,s_{i})$ exists in
$\mathcal{A}_{R2}$. After that, we can enumerate all the other elements with
the key by scanning the corresponding linear list. Thus, the total query time
is $O(\delta(n,\sigma)+(\log\log n)^{2}+\log\sigma_{i}+\beta_{\mathit{rem}})$
where $\beta_{\mathit{rem}}$ is the number of MUPSs of Type R2. Finally, we
show $\sigma_{i}\in O(\min\\{\sigma,\log n\\})$. Let us consider palindromes
in $T^{\prime}$ whose right arm covers position $i$. Those whose left arms
cover $i$ can be treated similarly. Any palindrome in $T^{\prime}$ whose right
arm covers $i$ is an expansion of some maximal palindrome in $T$ ending at
$i-1$. It is known that the number of possible characters immediately
preceding such maximal palindromes is $O(\log n)$ [15]. Therefore,
$\sigma_{i}\in O(\log n)$ holds, and thus, the query time is
$O(\delta(n,\sigma)+(\log\log n)^{2}+\beta_{\mathit{rem}})$.

#### Type R3.

Let $w=T[b..e]$ be a MUPS of $T$ and let $v=T[b+1..e-1]$. Further let
$T[b_{l1}..e_{l1}]$ and $T[b_{r1}..e_{r1}]$ be the leftmost and the rightmost
occurrence of $v$ in $T$ except for $T[b+1..e-1]$. We define interval
$\rho_{w}=\\{k\mid k\not\in[b+1,e-1]\text{ and }k\in[b_{r1},e_{l1}]\\}$. Note
that $\rho_{w}$ can be empty. See also Fig. 5 for illustration.

Figure 5: Illustration for $\rho_{w}$ of Type R3. The top arrow (resp. the
middle arrow) represents the leftmost (resp. rightmost) occurrence of $v$
except for $T[b+1..e-1]$. Also, the bottom arrow represents $T[b+1..e-1]$. In
this case, $\rho_{w}=[b_{r1},b]$.

If the editing position $i$ is in $\rho_{w}$, then the only occurrence of $v$
in $T^{\prime}$ is $T^{\prime}[b+1..e-1]$, i.e., $v$ is unique in
$T^{\prime}$. Thus, $w$ is a removed MUPS of Type R3. Contrary, if
$i\not\in[b,e]$ and $i\not\in\rho_{w}$, there are at least two occurrences of
$v$ in $T^{\prime}$, i.e., $w$ cannot be a MUPS of Type R3.

##### Preprocessing.

First, we compute the set of intervals $\mathcal{R}=\\{\rho_{w}\mid w\text{ is
a MUPS of }T\\}$. $\mathcal{R}$ can be computed by traversing over the suffix
tree of $T$ enhanced with additional explicit nodes, each of which represents
a substring $T[b+1..e-1]$ for each MUPS $T[b..e]$ of $T$. Also, we apply the
preprocessing for stabbing queries to $\mathcal{R}$. The total time for
preprocessing is $O(n)$.

##### Query.

Given a query $\mathit{sub}(i,s)$, compute all intervals in $\mathcal{R}$
stabbed by position $i$ by answering a stabbing query. They correspond to
MUPSs of Type R3. The query time is $O(1+\gamma_{\mathit{rem}})$, where
$\gamma_{\mathit{rem}}$ is the number of MUPSs of Type R3.

To summarize, we can compute all MUPSs to be removed after a single-character
substitution in $O(\delta(n,\sigma)+(\log\log
n)^{2}+\alpha_{\mathit{rem}}+\beta_{\mathit{rem}}+\gamma_{\mathit{rem}})$
time.

###  4.2 Computing MUPSs to be Added

Next, we propose an algorithm to detect MUPSs to be added after a
substitution. As in Section 4.1, we categorize MUPSs to be added into three
types:

A1)

A MUPS of $T^{\prime}$ that covers $i$.

A2)

A MUPS of $T^{\prime}$ that does not cover $i$ and is repeating in $T$.

A3)

A MUPS of $T^{\prime}$ that does not cover $i$ and is unique but not minimal
in $T$.

Furthermore, we categorize MUPSs of Type A1 into two sub-types:

A1-1)

A MUPS of $T^{\prime}$ that covers position $i$ in its arm.

A1-2)

A MUPS of $T^{\prime}$ centered at editing position $i$.

See Fig. 6 for illustration.

Figure 6:  Illustration for four types of MUPSs to be added. The red arrows
represent MUPSs. $w_{1\mathchar 45\relax 1}$, $w_{1\mathchar 45\relax 2}$,
$w_{2}$, and $w_{3}$ are MUPSs of Type A1-1, Type A1-2, Type A2, and Type A3
in $T^{\prime}$, respectively. Also, $v$ is the MUPS of $T$ that is a
contraction of $w_{3}$. It is unique in $T$, but is not unique in
$T^{\prime}$.

#### Type A1-1.

A MUPS of Type A1-1 is a contraction of some maximal palindrome in
$T^{\prime}$ covering editing position $i$ in its arm. Further, such a maximal
palindrome in $T^{\prime}$ corresponds to some 1-mismatch maximal palindrome
in $T$, which covers $i$ as a mismatch position. Thus, we preprocess for arms
of each 1-mismatch maximal palindrome in $T$. For MUPSs of Type A1, we utilize
the following observation:

######  Observation 1.

For any palindrome $v$ covering position $i$ in $T^{\prime}$, $v$ is unique in
$T^{\prime}$ if and only if $|\mathit{inbeg}_{T^{\prime},i}(v)|=1$ and
$|\mathit{xbeg}_{T^{\prime},i}(v)|=0$.

##### Preprocessing.

In the preprocessing phase, we first consider sorting extended arms of
1-mismatch maximal palindromes in $T$. Let $\mathit{EA}$ be the multiset of
strings that consists of the extended right arms and the reverse of the
extended left arms of all 1-mismatch maximal palindromes in $T$. Note that
each string in $\mathit{EA}$ can be represented in constant space since it is
a substring of $T$ or $T^{R}$. Let $\mathsf{MA}^{\prime}$ be a
lexicographically sorted array of all elements in $\mathit{EA}$. Here, the
order between the same strings can be arbitrary. Also, for each string in
$\mathit{EA}$, we consider a quadruple of the form
$(\mathit{par},\mathit{pos},\mathit{chr},\mathit{rnk})$ where
$\mathit{par}\in\\{\mathsf{odd},\mathsf{even}\\}$ represents the parity of the
length of the corresponded 1-mismatch maximal palindrome, $\mathit{pos}$ is
the mismatched position on the _opposite_ arm, $\mathit{chr}$ is the
mismatched character on the extended arm, and $\mathit{rnk}$ is the rank of
the extended arm in $\mathsf{MA}^{\prime}$. Let $\mathsf{MA}$ be a radix
sorted array of these quadruples. It can be seen that for each triple
$(p,i,s)$ of parity $p$, mismatched position $i$, and mismatched character
$s$, all elements corresponding to the triple are stored continuously in
$\mathsf{MA}$. We denote by $\mathsf{MA}_{p,i,s}$ the subarray of
$\mathsf{MA}$ consists of such elements. In other words, $\mathsf{MA}_{p,i,s}$
is a sorted array of extended arms of maximal palindromes of parity $p$
covering position $i$ in $T^{\prime}$ when the $i$-th character of $T$ is
substituted by $s$.

Now let us focus on odd-palindromes. Even-palindromes can be treated
similarly. We construct the suffix tree of $T$ and make the loci of strings in
$\mathit{EA}$ explicit. We also make the loci of the extended right arm of
every odd-palindrome in $T$ explicit. Simultaneously, we _mark_ the nodes
corresponding to the extended right arms and apply the preprocessing for the
nearest marked ancestor (NMA) queries to the marked tree. We denote the tree
by $\mathcal{ST}_{\mathit{odd}}$. Next, we initialize the set
$\mathcal{A}_{A1,1}=\emptyset$. The set $\mathcal{A}_{A1,1}$ will become an
index of MUPSs of Type A1-1 when the preprocessing is finished. For each non-
empty $\mathsf{MA}_{\mathsf{odd},i,s}$ and for each string $w$ in
$\mathsf{MA}_{\mathsf{odd},i,s}$, we do the followings: Let $x_{w}$ be the
odd-palindrome whose extended right arm is $w$ when $T[i]$ is substituted by
$s$. Let $u$ and $v$ are the preceding and the succeeding string of $w$ in
$\mathsf{MA}_{\mathsf{odd},i,s}$ (if such palindromes do not exist, they are
empty). Further let $\ell_{w}=\max\\{\mathit{lcp}(u,w),\mathit{lcp}(w,v)\\}$.
When $T[i]$ is substituted by $s$, any contraction $y$ of $x_{w}$ such that
$y$ covers position $i$ and the arm-length of $y$ is at least $\ell_{w}$ has
only one occurrence which covers position $i$ in $T^{\prime}$,
i.e.,$|\mathit{inbeg}_{T^{\prime},i}(y)|=1$. Next, we query the NMA for the
node corresponding to $w$ on $\mathcal{ST}_{\mathit{odd}}$. Let
$\ell^{\prime}_{w}$ be the length of the extended right arm obtained by the
NMA query. When $T[i]$ is substituted by $s$, any contraction $y^{\prime}$ of
$x_{w}$ such that the arm-length of $y^{\prime}$ is at least
$\ell^{\prime}_{w}$, has no occurrences which do not cover position $i$ in
$T^{\prime}$, i.e., $|\mathit{xbeg}_{T^{\prime},i}(y^{\prime})|=0$. Thus, by
Observation 1, the contraction $y^{\star}$ of $x_{w}$ of arm-length
$\max\\{\ell_{w},\ell^{\prime}_{w}\\}$ is a MUPS of Type A1-1 for the query
$\mathit{sub}(i,s)$, if such $y^{\star}$ exists. In such a case, we store the
information about $y^{\star}$ (i.e., its center and radius) into
$\mathcal{A}_{A1,1}$ using $(\mathsf{odd},i,s)$ as the key. After finishing
the above preprocessing for all strings in $\mathsf{MA}$, we sort all elements
in $\mathcal{A}_{A1,1}$ by their keys.

Since each element in $\mathit{EA}$ is a substring of $T\$T^{R}\\#$, they can
be sorted in $O(n+|\mathit{EA}|)=O(n)$ time by Corollary 2. Namely,
$\mathsf{MA}^{\prime}$ can be computed in linear time, and thus $\mathsf{MA}$
too. By Lemma 4, tree $\mathcal{ST}_{\mathit{odd}}$ can be constructed in
$O(n)$ time. Also, we can answer each NMA query and LCP query in constant time
after $O(n)$ time preprocessing. Hence, the total preprocessing time is
$O(n)$.

##### Query.

Given a query $\mathit{sub}(i,s)$, we compute all MUPSs of Type A1-1 by
searching for elements in $\mathcal{A}_{A1,1}$ with keys $(\mathsf{odd},i,s)$
and $(\mathsf{even},i,s)$. An element with each of the keys can be found in
$O(\log\min\\{\sigma,\log n\\})$ time. Thus, all MUPSs of Type A1-1 can be
computed in $O(\log\min\\{\sigma,\log n\\}+\alpha^{\prime}_{\mathit{add}})$
time where $\alpha^{\prime}_{\mathit{add}}$ is the number of MUPSs of Type
A1-1.

#### Type A1-2.

The MUPS of Type A1-2 is a contraction of the maximal palindrome in
$T^{\prime}$ centered at $i$. By definition, there is at most one MUPS of Type
A1-2.

##### Preprocessing.

In the preprocessing phase, we again construct $\mathsf{MA}$ and related data
structures as in Type A1-1. Further, we apply the $O(n)$-time preprocessing of
Lemma 10 for Problem 1. The total preprocessing time is $O(n)$.

##### Query.

Given substitution query $\mathit{sub}(i,s)$, we compute the MUPS centered at
$i$ in $T^{\prime}$ as follows (if it exists): It is clear that
$T^{\prime}[i..i]=s$ is the MUPS of Type A1-2 if $s$ is a unique character in
$T^{\prime}$. In what follows, we consider the other case. Let $w$ be the
maximal palindrome centered at $i$ in $T^{\prime}$. First, we compute the
maximum lcp value $\ell_{w}$ between $\mathsf{Rarm}_{w}$ and extended arms in
$\mathsf{MA}_{\mathsf{odd},i,s}$. Then, any contraction $y$ of $w$, such that
the arm-length of $y$ is at least $\ell_{w}$, has no occurrences which cover
position $i$ in $T^{\prime}$, i.e., $|\mathit{inbeg}_{T^{\prime},i}(y)|=1$. We
can compute $\ell_{w}$ in $O(\log\min\\{\sigma,\log n\\})$ time, combining LCE
queries and binary search. Note that $\mathsf{rarm}_{w}$ occurs at $i+1$ in
both $T$ and $T^{\prime}$ while $\mathsf{Rarm}_{w}$ might be absent from $T$.
Next we compute the arm-length $\ell^{\prime}_{w}$ of the shortest palindrome
$v$ such that $\mathit{center}(v)=i$ and
$|\mathit{xbeg}_{T^{\prime},i}(v)|=0$, i.e., $v$ is absent from $T$. Since the
contraction $\tilde{v}$ of $w$ of arm-length $\ell^{\prime}_{w}-1$ is the
longest palindrome such that $\mathit{center}(\tilde{v})=i$ and $\tilde{v}$
occurs in $T$, we can reduce the problem of computing $\ell^{\prime}_{w}$ to
Problem 1. Thus, we can compute $\ell^{\prime}_{w}$ in
$O(\delta(n,\sigma)+(\log\log n)^{2})$ time by Lemma 10. Similar to the case
of Type A1-1, by Observation 1, the contraction $y^{\star}$ of $x_{w}$ of arm-
length $\max\\{\ell_{w},\ell^{\prime}_{w}\\}$ is a MUPS of Type A1-2, if such
$y^{\star}$ exists. Therefore, the MUPS of Type A1-2 can be computed in
$O(\delta(n,\sigma)+(\log\log n)^{2})$ time.

#### Type A2.

A MUPS of Type A2 occurs at least twice in $T$, and there is only one
occurrence not covering editing position $i$. For a palindrome $w$ repeating
in $T$, let $T[b_{l1}..e_{l1}]$ and $T[b_{l2}..e_{l2}]$ be the leftmost and
the second leftmost occurrence of $w$ in $T$. Further, let $T[b_{r1}..e_{r1}]$
and $T[b_{r2}..e_{r2}]$ be the rightmost and the second rightmost occurrence
of $w$ in $T$. We define interval $\rho_{w}$ as the intersection of all
occurrences of $w$ except for the leftmost one, i.e., $\rho_{w}=\\{k\mid
k\not\in[b_{l1},e_{l1}]\text{ and }k\in[b_{r1},e_{l2}]\\}$ (see also Fig. 7).

Figure 7: Illustration for $\rho_{w}$ of Type A2. The top two arrows represent
the leftmost and the second leftmost occurrence of $w$. Also, the bottom two
arrows represent the second rightmost and the rightmost occurrence of $w$. In
this case, $\rho_{w}=[b_{r1},e_{l2}]$.

Similarly, we define interval $\tilde{\rho}_{w}$ as the intersection of all
occurrences of $w$ except for the rightmost one. Note that $\rho_{w}$ and
$\tilde{\rho}_{w}$ can be empty. Then, $w$ is unique after the $i$-th
character is edited if and only if $i\in\rho_{w}\cup\tilde{\rho}_{w}$. Thus,
any MUPS of Type A2 is a palindrome corresponding to some interval in
$\rho_{w}\cup\tilde{\rho}_{w}$ stabbed by $i$. To avoid accessing intervals
that do not correspond to the MUPSs to be added, we decompose each $\rho_{w}$.
It is easy to see that for any contraction $v$ of $w$,
$\rho_{v}\subset\rho_{w}$ holds. Also, if $T[i]$, with $i\in\rho_{v}$, is
edited, then both $w$ and $v$ become unique in $T^{\prime}$, i.e., $w$ cannot
be a MUPS of $T^{\prime}$. For each unique palindrome $w$ in $T$, we decompose
$\rho_{w}$ into at most three intervals
$\rho_{w}=\rho^{1}_{w}\rho_{w^{\prime}}\rho^{2}_{w}$ where
$w^{\prime}=w[2..|w|-1]$. Similarly, we decompose $\tilde{\rho}_{w}$ into
$\tilde{\rho}_{w}=\tilde{\rho}^{1}_{w}\tilde{\rho}_{w^{\prime}}\tilde{\rho}^{2}_{w}$.
Then, $w$ is a MUPS of Type A2 if and only if
$i\in\rho^{1}_{w}\cup\rho^{2}_{w}\cup\tilde{\rho}^{1}_{w}\cup\tilde{\rho}^{2}_{w}$.

##### Preprocessing.

In the preprocessing phase, we first construct the eertree of $T$ and the
suffix tree of $T$ enhanced with additional explicit nodes for all distinct
palindromes in $T$. Next, we compute at most four (leftmost, second leftmost,
rightmost, second rightmost) occurrences of each palindrome in $T$ by
traversing the enhanced suffix tree. At the same time, we compute $\rho_{w}$
and $\tilde{\rho}_{w}$ for each palindrome in $w$. Next, we sequentially
access distinct palindromes by traversing $\mathsf{EERTREE}(T)$ in a pre-order
manner. Then, for each palindrome $w$, we decompose $\rho_{w}$ and
$\tilde{\rho_{w}}$ based on the rules as mentioned above. Finally, we apply
the preprocessing for stabbing queries to the $O(n)$ intervals obtained. The
total preprocessing time is $O(n)$.

##### Query.

Given a query $\mathit{sub}(i,s)$, we compute all intervals stabbed by
position $i$. The palindromes corresponding to the intervals are MUPSs of Type
A2. Hence, the query time is $O(1+\beta_{\mathit{add}})$, where
$\beta_{\mathit{add}}$ is the number of MUPSs of Type A2.

#### Type A3.

A MUPS of Type A3 is unique but not minimal in $T$. Such a unique palindrome
$u$ in $T$ contains a MUPS $w\neq u$ of $T$ as a contraction. Since $u$ is a
MUPS of $T^{\prime}$, $w$ is repeating in $T^{\prime}$, i.e., $w$ is a removed
MUPS of Type R2. Contrary, consider a MUPS $w$ of Type R2, which is repeating
in $T^{\prime}$. Then, the shortest unique expansion of $w$ in $T^{\prime}$ is
an added MUPS of Type A3, if it exists. The preprocessing for Type A3 is
almost the same as for Type R2. We store a bit more information for Type A3 in
addition to the information in $\mathcal{A}_{R2}$.

##### Preprocessing.

In the preprocessing phase, we first apply the $O(n)$-time preprocessing of
Lemma 10 for Problem 1. Next, we initialize the set
$\mathcal{A}_{A3}=\emptyset$. This set $\mathcal{A}_{A3}$ will become an index
of MUPSs of Type A3 when the preprocessing is finished. For each MUPS
$w=T[b..e]$ of $T$, we process the followings: For the beginning position
$j\neq b$ of each occurrence of $\mathsf{Larm}_{w}$ in $T$, we compute the lcp
value $\ell_{j}$ between $T[j+|\mathsf{Larm}_{w}|..|T|]\$$ and $T[\lceil
c\rceil..|T|]\$$ with allowing one mismatch where $c$ is the center of $w$ in
$T$. If $\ell_{j}$ is smaller than $\mathsf{rarm}_{w}$, then we do nothing for
this occurrence since $w$ cannot occur at $j$ after any single-character
substitution. Otherwise, let $q=j+|\mathsf{Larm}_{w}|-1+d$ be the first
mismatched position in $T$. When the $q$-th character of $T$ is substituted by
the character $\mathsf{rarm}_{w}[d]$, $w=T[b..e]$ occurs at $j\neq b$, i.e.,
it is a MUPS of Type R2. Unlike for Type R2, we add the _pair_ of MUPS and
(1-mismatched) lcp value $(T[b..e],\ell_{j})$ into $\mathcal{A}_{A3}$ with the
pair of index and character $(q,\mathsf{rarm}_{w}[d])$ as the key. In
addition, symmetrically, we update $\mathcal{A}_{A3}$ for each occurrence of
$\mathsf{Rarm}_{w}$ in $T$. After finishing the above processes for every MUPS
of $T$, we then sort the elements of $\mathcal{A}_{A3}$ by radix sort on the
keys. If there are multiple identical elements with the same key, we unify
them into a single element. Also, if there are multiple elements with the same
key, we store them in a linear list. By Lemma 3, the total number of
occurrences of arms of MUPSs is $O(n)$, and hence, the total preprocessing
time is $O(n)$.

##### Query.

Given a query $\mathit{sub}(i,s)$, we query Problem 1 with the same pair
$(i,s)$ as the input. Then, we complete checking whether there exists a MUPS
of Type A3 centered at $i$. For the remaining MUPSs of Type 3, we retrieve the
MUPSs of Type A3 using the index $\mathcal{A}_{A3}$ as in the query algorithm
for Type R2. This can be done in $O(\log\min\\{\sigma,\log
n\\}+\gamma_{\mathit{add}})$ time where $\gamma_{\mathit{add}}$ is the number
of MUPSs of Type A3. Therefore, the total query time of Type A3 is
$O(\delta(n,\sigma)+(\log\log n)^{2}+\gamma_{\mathit{add}})$.

To summarize, we can compute all MUPSs to be added after a single-character
substitution in $O(\delta(n,\sigma)+(\log\log
n)^{2}+\alpha^{\prime}_{\mathit{add}}+\beta_{\mathit{add}}+\gamma_{\mathit{add}})$
time. Then, combining the results of Section 4.1 with the above results, we
obtain the following theorem:

######  Theorem 3.

After $O(n)$-time preprocessing, we can compute the set of MUPSs after a
single-character substitution in $O(\delta(n,\sigma)+(\log\log
n)^{2}+d)\subset O(\log n)$ time where $d$ is the number of changes of MUPSs.

###  4.3 Alternative Algorithm for Problem 1

The query time of Theorem 3 is dominated by the time to answer Problem 1.
Here, we introduce another solution for Problem 1 utilizing _nearest colored
ancestor queries_ instead of path-tree LCE queries.

##### Preprocessing for Problem 1.

We first construct the suffix tree of $T\$$. Also, for each odd-palindrome in
$T$, we make the locus of the right arm explicit and label the node with the
pair of the center character and the binary flag that indicates if the
palindrome is a MUPS. We regard the pair as the _color_ of the node.
Furthermore, we apply a preprocessing for NCA queries to the colored tree222
There can be a node with multiple colors in the tree. However, we can easily
avoid such a situation by copying a node with $k$ colors to $k$ nodes. Also,
in the case of Problem 1, the cumulative total number of colored nodes is
$O(n)$. . The preprocessing time is $O(n+c_{\mathsf{nca}}(n,\sigma))$, where
$c_{\mathsf{nca}}(n,\sigma)$ is the preprocessing time for NCA queries.

##### Query for Problem 1.

Given a substitution query $\mathit{sub}(i,s)$, we start at the node
corresponding to $\mathsf{rarm}_{w}$ where $w$ is the maximal palindrome in
$T$ centered at $i$. We then compute the nearest ancestor $V$ colored with
$(s,\mathsf{0})$ by using NCA query. If such node $V$ exists, palindrome
$P=\mathit{str}(V)^{R}\cdot s\cdot\mathit{str}(V)$ is the answer of the former
part of Problem 1 where $\mathit{str}(V)$ denotes the string corresponding to
$V$ in the enhanced suffix tree of $T\$$. Also, we query NCA $(s,\mathsf{1})$
from $V$. We can determine if $P$ is unique, and if it is unique, we can find
the MUPS contained in $P$. The query time is $O(q_{\mathsf{nca}}(n,\sigma))$
where $q_{\mathsf{nca}}(n,\sigma)$ is the query time for NCA.

Let $s_{\mathsf{nca}}(n,\sigma)$ denote the space for the NCA data structure.
We obtain the following theorem:

######  Theorem 4.

After $O(n+c_{\mathsf{nca}}(n,\sigma))$-time and
$O(n+s_{\mathsf{nca}}(n,\sigma))$-space preprocessing, we can compute the set
of MUPSs after a single-character substitution in
$O(q_{\mathsf{nca}}(n,\sigma)+\log\min\\{\sigma,\log n\\}+d)$ time.

The results for NCA queries in Lemmas 5 and 6 can be plugged into the
functions $c_{\mathsf{nca}}$, $q_{\mathsf{nca}}$, and $s_{\mathsf{nca}}$. In
addition, even when a general case, we can handle $\delta(n,\sigma)$ as a
constant by utilizing a perfect hashing [13] after $O(n\log\log n)$-time or
$O(n)$-expected time preprocessing. Table 1 lists different representations of
the time/space complexities of Theorems 3 and 4. We emphasize that our
algorithm runs in optimal $O(1+d)$ time when $\sigma$ is constant.

######  Corollary 3.

If $\sigma\in O(1)$, after $O(n)$-time and $O(n)$-preprocessing, we can
compute the set of MUPSs after a single-character substitution in $O(1+d)$
time.

| Time |  |
---|---|---|---
$\sigma$ | Construction | Query | Space | Ref.
$n^{O(1)}$ | $O(n)$ | $O(\log\sigma+(\log\log n)^{2}+d)$ | $O(n)$ | Theorem 3, 1
$n^{O(1)}$ | $O(n\log\log n)$ | $O(\log\log n+d)$ | $O(n)$ | Theorem 4, Lemma 5
$n^{O(1)}$ | expected $O(n)$ | $O(\log\log n+d)$ | $O(n)$ | Theorem 4, Lemma 5
$O(n)$ | $O(n)$ | $O((\log\log n)^{2}+d)$ | $O(n)$ | Theorem 3, 1
$O(\log n)$ | $O(n)$ | $O(\log\log n+d)$ | $O(n)$ | Theorem 4, Lemma 6
$O(1)$ | $O(n)$ | $O(1+d)$ | $O(n)$ | Theorem 4, Lemma 6
Table 1:  Concrete complexities of our algorithms for the problem of computing
MUPSs after a single-character substitution. All the above results require
only linear space. Each query time is $O(\log n)$ since $\log\sigma\in O(\log
n)$ and $d\in O(\log n)$.

##  5 Conclusions and Future Work

In this paper, we dealt with the problem of updating the set of MUPSs of a
string after a single-character substitution. We showed that the number $d$ of
changes of MUPSs after a single-character substitution is $O(\log n)$.
Furthermore, we presented an algorithm that uses $O(n)$ time and space for
preprocessing, and updates the set of MUPSs in $O(\log\sigma+(\log\log
n)^{2}+d)$ time where $\sigma$ is the alphabet size. We also proposed a
variant of the algorithm, which runs in optimal $O(1+d)$ time when the
alphabet size is constant.

Our future work includes the following:

  * (1)

Can our algorithm be adapted to the cases of insertions and deletions?

  * (2)

Can we extend our algorithm to a fully dynamic setting? It is interesting
whether the techniques in [5, 2] can be utilized in the dynamic version of the
MUPS problem.

## Acknowledgements

We would like to thank Associate Professor Shunsuke Inenaga (Kyushu
University) for the valuable discussions on simplifying our algorithms. This
work was supported by the JSPS KAKENHI Grant Numbers JP20J21147 (MF) and
JP20J11983 (TM).

## References

  * [1] Paniz Abedin, Sahar Hooshmand, Arnab Ganguly, and Sharma V. Thankachan.  The heaviest induced ancestors problem revisited.  In Gonzalo Navarro, David Sankoff, and Binhai Zhu, editors, Annual Symposium on Combinatorial Pattern Matching, CPM 2018, July 2-4, 2018 - Qingdao, China, volume 105 of LIPIcs, pages 20:1–20:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  doi:10.4230/LIPIcs.CPM.2018.20.
  * [2] Amihood Amir and Itai Boneh.  Dynamic palindrome detection.  CoRR, abs/1906.09732, 2019.  URL: http://arxiv.org/abs/1906.09732, arXiv:1906.09732.
  * [3] Amihood Amir, Itai Boneh, Panagiotis Charalampopoulos, and Eitan Kondratovsky.  Repetition detection in a dynamic string.  In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 5:1–5:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ESA.2019.5.
  * [4] Amihood Amir, Panagiotis Charalampopoulos, Costas S. Iliopoulos, Solon P. Pissis, and Jakub Radoszewski.  Longest common factor after one edit operation.  In Gabriele Fici, Marinella Sciortino, and Rossano Venturini, editors, String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Palermo, Italy, September 26-29, 2017, Proceedings, volume 10508 of Lecture Notes in Computer Science, pages 14–26. Springer, 2017.  doi:10.1007/978-3-319-67428-5\\_2.
  * [5] Amihood Amir, Panagiotis Charalampopoulos, Solon P. Pissis, and Jakub Radoszewski.  Longest common substring made fully dynamic.  In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 6:1–6:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.  doi:10.4230/LIPIcs.ESA.2019.6.
  * [6] Alberto Apostolico, Dany Breslauer, and Zvi Galil.  Parallel detection of all palindromes in a string.  Theor. Comput. Sci., 141(1&2):163–173, 1995.  doi:10.1016/0304-3975(94)00083-U.
  * [7] Philip Bille, Pawel Gawrychowski, Inge Li Gørtz, Gad M. Landau, and Oren Weimann.  Longest common extensions in trees.  Theor. Comput. Sci., 638:98–107, 2016.  doi:10.1016/j.tcs.2015.08.009.
  * [8] Philip Bille, Gad M. Landau, Rajeev Raman, Kunihiko Sadakane, Srinivasa Rao Satti, and Oren Weimann.  Random access to grammar-compressed strings and trees.  SIAM J. Comput., 44(3):513–539, 2015.  doi:10.1137/130936889.
  * [9] Panagiotis Charalampopoulos, Pawel Gawrychowski, and Karol Pokorski.  Dynamic longest common substring in polylogarithmic time.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 27:1–27:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.ICALP.2020.27.
  * [10] Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń.  Internal dictionary matching.  Algorithmica, 2021.  doi:10.1007/s00453-021-00821-y.
  * [11] Xavier Droubay, Jacques Justin, and Giuseppe Pirillo.  Episturmian words and some constructions of de Luca and Rauzy.  Theor. Comput. Sci., 255(1-2):539–553, 2001.  doi:10.1016/S0304-3975(99)00320-5.
  * [12] Martin Farach-Colton, Paolo Ferragina, and S. Muthukrishnan.  On the sorting-complexity of suffix tree construction.  J. ACM, 47(6):987–1011, 2000.  doi:10.1145/355541.355547.
  * [13] Michael L. Fredman, János Komlós, and Endre Szemerédi.  Storing a sparse table with $O(1)$ worst case access time.  J. ACM, 31(3):538–544, 1984.  doi:10.1145/828.1884.
  * [14] Mitsuru Funakoshi and Takuya Mieno.  Minimal unique palindromic substrings after single-character substitution.  In Thierry Lecroq and Hélène Touzet, editors, String Processing and Information Retrieval - 28th International Symposium, SPIRE 2021, Lille, France, October 4-6, 2021, Proceedings, volume 12944 of Lecture Notes in Computer Science, pages 33–46. Springer, 2021.  doi:10.1007/978-3-030-86692-1\\_4.
  * [15] Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Computing longest palindromic substring after single-character or block-wise edits.  Theor. Comput. Sci., 859:116–133, 2021.  doi:10.1016/j.tcs.2021.01.014.
  * [16] Leszek Gasieniec, Marek Karpinski, Wojciech Plandowski, and Wojciech Rytter.  Efficient algorithms for Lempel-Ziv encoding.  In Rolf Karlsson and Andrzej Lingas, editors, Algorithm Theory — SWAT’96, pages 392–403, Berlin, Heidelberg, 1996. Springer Berlin Heidelberg.
  * [17] Pawel Gawrychowski, Tomohiro I, Shunsuke Inenaga, Dominik Köppl, and Florin Manea.  Tighter bounds and optimal algorithms for all maximal $\alpha$-gapped repeats and palindromes - finding all maximal $\alpha$-gapped repeats and palindromes in optimal worst case time on integer alphabets.  Theory Comput. Syst., 62(1):162–191, 2018.  doi:10.1007/s00224-017-9794-5.
  * [18] Pawel Gawrychowski, Gad M. Landau, Shay Mozes, and Oren Weimann.  The nearest colored node in a tree.  Theor. Comput. Sci., 710:66–73, 2018.  doi:10.1016/j.tcs.2017.08.021.
  * [19] Hiroe Inoue, Yuto Nakashima, Takuya Mieno, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Algorithms and combinatorial properties on shortest unique palindromic substrings.  J. Discrete Algorithms, 52-53:122–132, 2018.  doi:10.1016/j.jda.2018.11.009.
  * [20] Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen.  A linear-time algorithm for seeds computation.  ACM Trans. Algorithms, 16(2):27:1–27:23, 2020.  doi:10.1145/3386369.
  * [21] Glenn K. Manacher.  A new linear-time ”on-line” algorithm for finding the smallest initial palindrome of a string.  J. ACM, 22(3):346–351, 1975.  doi:10.1145/321892.321896.
  * [22] Wataru Matsubara, Shunsuke Inenaga, Akira Ishino, Ayumi Shinohara, Tomoyuki Nakamura, and Kazuo Hashimoto.  Efficient algorithms to compute compressed longest common substrings and compressed palindromes.  Theor. Comput. Sci., 410(8-10):900–913, 2009.  doi:10.1016/j.tcs.2008.12.016.
  * [23] Takuya Mieno, Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Palindromic trees for a sliding window and its applications.  Information Processing Letters, 173:106174, 2022.  doi:https://doi.org/10.1016/j.ipl.2021.106174.
  * [24] Mikhail Rubinchik and Arseny M. Shur.  EERTREE: an efficient data structure for processing palindromes in strings.  Eur. J. Comb., 68:249–265, 2018.  doi:10.1016/j.ejc.2017.07.021.
  * [25] Mikhail Rubinchik and Arseny M. Shur.  Palindromic k-factorization in pure linear time.  In Javier Esparza and Daniel Král’, editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 81:1–81:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.MFCS.2020.81.
  * [26] Jens M. Schmidt.  Interval stabbing problems in small integer ranges.  In Yingfei Dong, Ding-Zhu Du, and Oscar H. Ibarra, editors, Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, volume 5878 of Lecture Notes in Computer Science, pages 163–172. Springer, 2009.  doi:10.1007/978-3-642-10631-6\\_18.
  * [27] Yuki Urabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Longest Lyndon substring after edit.  In Gonzalo Navarro, David Sankoff, and Binhai Zhu, editors, Annual Symposium on Combinatorial Pattern Matching, CPM 2018, July 2-4, 2018 - Qingdao, China, volume 105 of LIPIcs, pages 19:1–19:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  doi:10.4230/LIPIcs.CPM.2018.19.
  * [28] Kiichi Watanabe, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda.  Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings.  Theory Comput. Syst., 64(7):1273–1291, 2020.  doi:10.1007/s00224-020-09980-x.
  * [29] Peter Weiner.  Linear pattern matching algorithms.  In 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15-17, 1973, pages 1–11. IEEE Computer Society, 1973\.  doi:10.1109/SWAT.1973.13.


$\mathsf{QMIP}^{*}$ $\mathsf{MIP}^{*}$

# A Simple Proof of $\mathsf{PreciseQMA}=\mathsf{PSPACE}$

Yulong Li
Columbia University

###### Abstract

We give an alternative proof of $\mathsf{PreciseQMA}=\mathsf{PSPACE}$, first
proved by Fefferman and Lin (_Innov. Theor. Comp. Sci. 2018_), where
$\mathsf{PreciseQMA}$ is the class Quantum Merlin-Arthur with inverse
exponential completeness-soundness gap. We adapt the proof of Quantum Cook-
Levin Theorem to prove the inclusion
$\mathsf{PSPACE}\subseteq\mathsf{PreciseQMA}$.

##  1 Introduction

A crucial focus of quantum complexity theory is to study quantum counterparts
of classical complexity classes. By comparing the classical and quantum
complexity classes, we may better understand the power of quantum computation
models. One particularly important quantum complexity class is Quantum Merlin-
Arthur ($\mathsf{QMA}$). It is the quantum analog of Merlin-Arthur
($\mathsf{MA}$), and it can also be seen as the quantum equivalent of
$\mathsf{NP}$ because of the close relationship between the canonical
$\mathsf{NP}$-complete problem, the satisfiability problem, and the natural
$\mathsf{QMA}$-complete problem, the local Hamiltonian problem. The formal
definition of $\mathsf{QMA}$ is as following.

######  Definition 1.

A promise problem $L=(L_{yes},L_{no})$ is in $\mathsf{QMA}(c,s)$ if there
exists a uniform family of quantum circuits
$\\{V_{x}\\}_{x}\in\\{0,1\\}^{|x|}$, each of size at most $poly(|x|)$ and
acting on $poly(|x|)$ qubits, such that: For $x\in L_{yes}$, there exists a
$poly(|x|)$-qubit state $\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle$ such
that $\Pr[V_{x}\text{ accepts
$\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle$}]\geq c$; for $x\in L_{no}$,
for all $poly(|x|)$-qubit state
$\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle$: $\Pr[V_{x}\text{ accepts
$\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle$}]\leq s$. The parameter $c$
and $s$ are known as the completeness and soundness of the problem,
respectively, and the quantity $c-s$ is known as the _completeness-soundness
gap_ , or _gap_ for short. $\mathsf{QMA}$ is typically defined as
$\mathsf{QMA}(c,s)$ for all $c-s$ that is inverse polynomial in $n$.

One interesting question to ask is how will the precision of values of $c$ and
$s$ change the power of $\mathsf{QMA}$. Kitaev showed that as long as the gap
$c-s$ is at least inverse polynomial, we can amplify the gap to a constant
[KSV02]. It’s then natural to ask what if the promise gap is much smaller.
Surprisingly, Fefferman and Lin showed that $\mathsf{QMA}$ class with inverse
exponentially small gap, denoted as $\mathsf{PreciseQMA}$, is equal to
$\mathsf{PSPACE}$ [FL16a].

######  Definition 2.

$\mathsf{PreciseQMA}=\cup_{c,s\in[0,1],c-s\geq 2^{-poly(n)}}\mathsf{QMA}(c,s)$
where $n$ is the length of the input.

######  Theorem 3 ( [FL16a]).

$\mathsf{PreciseQMA}=\mathsf{PSPACE}$

On the other hand, we can upper bound $\mathsf{MA}_{\mathsf{exp}}$, the
classical analogy of $\mathsf{PreciseQMA}$ with $\mathsf{NP}^{\mathsf{PP}}$,
which is widely believed to be strictly contained in $\mathsf{PSPACE}$. This
implies a possible separation between the classical complexity class
$\mathsf{MA}$ and the quantum analogue $\mathsf{QMA}$, at least in the inverse
exponential gap setting.

We give an alternate, arguably simpler, proof that
$\mathsf{PreciseQMA}=\mathsf{PSPACE}$, specifically the direction
$\mathsf{PreciseQMA}\supseteq\mathsf{PSPACE}$. The direction
$\mathsf{PreciseQMA}\subseteq\mathsf{PSPACE}$ is fairly intuitive. Given a
polynomial size proof state and polynomial time verification algorithm, we can
simulate the protocol in polynomial space by guessing the proof and performing
amplification even when the gap is inverse exponential [FL16a]. The reverse
direction, $\mathsf{PreciseQMA}\supseteq\mathsf{PSPACE}$, is more involved. In
Fefferman and Lin’s original proof, they define the problem Gapped Succinct
Matrix Singularity (GSMS), which, informally speaking, takes in a sparse
matrix whose smallest eigenvalue is promised to be either $0$ or at least
inverse exponential and decides between the two cases. They gave a
$\mathsf{PreciseQMA}$ protocol for $GSMS$ based on Hamiltonian simulation and
phase estimation and showed that $GSMS$ is $\mathsf{PSPACE}$-hard by encoding
the configuration graph of a $\mathsf{PSPACE}$ machine into a sparse matrix
that satisfies the promise gap of $GSMS$. In a follow-up paper by Fefferman
and Lin, they prove a more general result about unitary quantum space, of
which $\mathsf{PreciseQMA}=\mathsf{PSPACE}$ is a corollary. But their main
result still requires a nontrivial reduction to a general linear algebra
problem [FL16b].

The proof inspired us to encode the computation of a $\mathsf{PSPACE}$ machine
_directly_ using the Feynman-Kitaev circuit-to-Hamiltonian construction
[KSV02]. This proof technique was used to show the QMA-completeness of the
Local Hamiltonian problem. In our opinion, the direct encoding of the
computation history and the close relationship between Hamiltonian problems
and $\mathsf{QMA}$ make the proof
$\mathsf{PSPACE}\subseteq\mathsf{PreciseQMA}$ more intuitive and sidestep the
linear algebraic problem of GSMS. As an easy corollary of the proof, we show
that $\mathsf{PreciseQMA}$ with perfect completeness, denoted as
$\mathsf{PreciseQMA}^{c=1}$, is equal to $\mathsf{PreciseQMA}$ (Corollary 10),
which is first shown in [FL16b]. Note that perfect completeness does not
change the class $\mathsf{MA}$ [ZF87], the classical analogue of
$\mathsf{QMA}$, but it is an open problem whether $\mathsf{QMA}$ is equal to
$\mathsf{QMA}^{c=1}$. In fact, Aaronson showed that
$QMA\neq\mathsf{QMA}^{c=1}$ relative to a quantum oracle [Aar08].

##  2 Reversible space computation

One crucial difference between classical and quantum computation is that for
quantum circuits, we often require the operations to be unitaries which are
inherently reversible, while we typically do not have reversibility
constraints for Turing machines. Thus, we need the following theorem about
reversible classical computation.

######  Definition 4.

We say a promise problem $L=(L_{yes},L_{no})$ is in $\mathsf{revPSPACE}$
(reversible polynomial space) if it can be decided by a polynomial space
reversible Turing machine, i.e., a machine for which every configuration has
at most one immediate predecessor.

######  Theorem 5 ( [Ben89]).

$\mathsf{PSPACE}=\mathsf{revPSPACE}$

Theorem 5 shows that without loss of generality a polynomial-space computation
can be made reversible, and thus can be simulated by a unitary quantum circuit
with perfect completeness and soundness.

######  Corollary 6.

If $L\in\mathsf{PSPACE}$, $L$ is recognized by a family of unitary quantum
circuits $\\{C_{n}\\}$ which run in exponential time and polynomial space in
$n$; moreover, if $x\in L$, then the circuit accepts with probability $1$,
otherwise it accepts with probability $0$.

##  3 QMA with exponentially small gap

Our first step of the proof is to construct a Hamiltonian with inverse
exponential promise gap given a $\mathsf{PSPACE}$ machine (or equivalently a
quantum circuit using exponential time and polynomial space) based on history
state construction, which is shown in Lemma. 7. The second step is to give a
$\mathsf{PreciseQMA}$ protocol for the Local Hamiltonian Problem with inverse
exponential promise gaps, which is Algorithm 8.

######  Lemma 7.

If $L$ is recognized with perfect completeness and soundness by a family of
quantum circuits $\\{C_{n}\\}$ which run in exponential time and polynomial
space in $n$, then for all $x\in\\{0,1\\}^{n}$, there exists a Hamiltonian
$H_{x}$ such that, if $x\in L$,
$\min_{\psi}\langle\mspace{0.5mu}\psi\mspace{0.5mu}\rvert
H_{x}\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle=0$, and if $x\notin L$,
$\min_{\psi}\langle\mspace{0.5mu}\psi\mspace{0.5mu}\rvert
H_{x}\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle\geq\frac{1}{2(T+1)^{3}}$.

Proof: We adapt the Quantum Cook-Levin Theorem to the setting of
exponentially-long quantum computations. The idea is to construct a
Hamiltonian to check to check whether a state encodes a valid history state of
a circuit.

Construction:

Suppose the quantum circuit $C_{n}$ that acts on $S(n)$ qubits and consists of
$T(n)=\exp^{poly(n)}$ unitary two-qubit gates, $U_{1},\cdots,U_{T}$. For
$b\in\\{0,1\\},i\in[S(n)]$, we define
$\Pi_{i}^{\lvert\mspace{0.5mu}b\mspace{0.5mu}\rangle}$ to be the projection
operator that operates on qubit number $i$ and projects on the subspace
spanned by $\lvert\mspace{0.5mu}b\mspace{0.5mu}\rangle$.

$H_{in}^{i}=\Pi_{i}^{\lvert\mspace{0.5mu}\lnot
x_{i}\mspace{0.5mu}\rangle}\otimes\lvert\mspace{0.5mu}0\mspace{0.5mu}\rangle\\!\langle\mspace{0.5mu}0\mspace{0.5mu}\rvert_{C}$
$H_{out}=\Pi_{1}^{\lvert\mspace{0.5mu}0\mspace{0.5mu}\rangle}\otimes\lvert\mspace{0.5mu}T\mspace{0.5mu}\rangle\\!\langle\mspace{0.5mu}T\mspace{0.5mu}\rvert_{C}$
$H_{prop}^{t}=\frac{1}{2}(I\otimes\lvert\mspace{0.5mu}t\mspace{0.5mu}\rangle\\!\langle\mspace{0.5mu}t\mspace{0.5mu}\rvert+I\otimes\lvert\mspace{0.5mu}t-1\mspace{0.5mu}\rangle\\!\langle\mspace{0.5mu}t-1\mspace{0.5mu}\rvert-
U_{t}\otimes\lvert\mspace{0.5mu}t\mspace{0.5mu}\rangle\\!\langle\mspace{0.5mu}t-1\mspace{0.5mu}\rvert-
U_{t}^{\dagger}\otimes\lvert\mspace{0.5mu}t-1\mspace{0.5mu}\rangle\\!\langle\mspace{0.5mu}t\mspace{0.5mu}\rvert)$
$H_{x}=\sum_{i=1}^{n}H_{in}^{i}+H_{out}+\sum_{t=1}^{T}H_{prop}^{t}$

for $t\in\\{0,1,\dots,T\\}$, where
$\lvert\mspace{0.5mu}t\mspace{0.5mu}\rangle_{C}$ is the binary representation
of $t$ taking $\log T$ qubits. If $x\in L$, we have the history of computation
$\lvert\mspace{0.5mu}\eta\mspace{0.5mu}\rangle=\frac{1}{T+1}\sum_{i=1}^{T}U_{t}\cdots
U_{1}\lvert\mspace{0.5mu}\chi\mspace{0.5mu}\rangle\otimes\lvert\mspace{0.5mu}t\mspace{0.5mu}\rangle$
where
$\lvert\mspace{0.5mu}\chi\mspace{0.5mu}\rangle=\lvert\mspace{0.5mu}x\mspace{0.5mu}\rangle\otimes\lvert\mspace{0.5mu}0\mspace{0.5mu}\rangle^{\otimes
S-n}$ is the start state encoding the work space including an input $x$. It is
straightforward to check that $\langle\mspace{0.5mu}\eta\mspace{0.5mu}\rvert
H\lvert\mspace{0.5mu}\eta\mspace{0.5mu}\rangle=0$ if $x\in L$ using the fact
that $C_{n}$ accepts $x$ with probability $1$ if $x\in L$. If $x\notin L$,
following the analysis in [AN02], one can show that
$\langle\mspace{0.5mu}\psi\mspace{0.5mu}\rvert
H\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle\geq\frac{1}{2(T+1)^{3}}$ for
all $\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle$.

######  Algorithm 8.

We give a $\mathsf{PreciseQMA}$ protocol, which given a polynomial size proof
state, check the eigenvalue of $H_{x}$ defined in 7 in polynomial time such
that if
$\min_{\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle}\langle\mspace{0.5mu}\psi\mspace{0.5mu}\rvert
H_{x}\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle=0$, always accepts;
otherwise, reject with at least inverse exponential probability.

  1. 1.

Pick $y\in[T+n+2]$ uniformly at random.

  2. 2.

Define

$H_{test}(y)=\begin{cases}H_{prop}^{y-1},&y\in[T+1]\\\
H_{in}^{y-T-1},&y\in[T+2,T+n+1]\\\ H_{out},&y=T+n+2\end{cases}$

  3. 3.

If $H_{test}(y)=H_{in}^{i}$ or $H_{test}=H_{out}$, which are projections onto
standard basis, measure $\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle$,
reject if the measurement is in the projected space.

  4. 4.

If $H_{test}(y)=H_{prop}^{t}$, we apply several transformations. Note that

$R_{t}^{\dagger}H_{prop}^{t}R_{t}=\frac{1}{2}I\otimes(\lvert\mspace{0.5mu}t\mspace{0.5mu}\rangle-\lvert\mspace{0.5mu}t-1\mspace{0.5mu}\rangle)(\langle\mspace{0.5mu}t\mspace{0.5mu}\rvert-\langle\mspace{0.5mu}t-1\mspace{0.5mu}\rvert)$

where $R=\sum_{t=0}^{T}U_{t}U_{t-1}\cdots
U_{1}\otimes\lvert\mspace{0.5mu}t\mspace{0.5mu}\rangle\\!\langle\mspace{0.5mu}t\mspace{0.5mu}\rvert$.
Thus, we can design a procedure that involves controlled unitaries of $U_{t}$
and $U_{t+1}$ that results in measurement of $1$ with probability
$\langle\mspace{0.5mu}\psi\mspace{0.5mu}\rvert
H_{prop}^{t}\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle$ in which case we
reject.

The total probability of rejection is

$\frac{1}{T+n+2}\sum_{y=1}^{T+n+2}\langle\mspace{0.5mu}\psi\mspace{0.5mu}\rvert
H_{test}(y)\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle=\frac{1}{T+n+2}\langle\mspace{0.5mu}\psi\mspace{0.5mu}\rvert
H_{x}\lvert\mspace{0.5mu}\psi\mspace{0.5mu}\rangle$

For $x\in L$, this equals to $0$; for $x\notin L$, this is at least
$\exp(-\mathrm{poly}(n))$.

Finally, the result immediately implies that we can always boost the
completeness of a $\mathsf{PreciseQMA}$ protocol to $1$, which is first shown
in [FL16b].

######  Definition 9.

$\mathsf{PreciseQMA}^{c=1}=\mathsf{QMA}_{poly}(1,1-2^{-poly})$

######  Corollary 10.

$\mathsf{PreciseQMA}$= $\mathsf{PreciseQMA}^{c=1}$

###### Proof.

For any $L\in\mathsf{PreciseQMA}$, by Theorem 3 and Corollary 6, we have a
uniform family of unitary quantum circuits $\\{C_{n}\\}$ which run in
exponential time and polynomial space in $n$ that accepts a string in $L$ with
probability $1$ and rejects otherwise. Then by Lemma 7 and Algorithm 8, we
have a $\mathsf{PreciseQMA}^{c=1}$ protocol for $L$. ∎

However, this is an indirect reduction that goes through $\mathsf{PSPACE}$. It
is thus interesting to ask whether there is a direct reduction from
$\mathsf{PreciseQMA}$ to $\mathsf{PreciseQMA}^{c=1}$.

##  4 Acknowledgements

We are very thankful to Henry Yuen for introducing the problem and his
guidance throughout the process. We are also thankful for helpful discussions
with Adrian She at various stages of the work.

## References

  * [Aar08] Scott Aaronson.  On perfect completeness for QMA.  Quantum Information and Computation, 2008.
  * [AN02] Dorit Aharonov and Tomer Naveh.  Quantum NP - a survey, 2002.
  * [Ben89] Charles H. Bennett.  Time/space trade-offs for reversible computation.  Society for Industrial and Applied Mathematics, 18:766–776, 1989\.
  * [FL16a] Bill Fefferman and Cedric Lin.  Quantum Merlin Arthur with exponentially small gap.  arXiv preprint arXiv:1601.01975, 2016.
  * [FL16b] Bill Fefferman and Cedric Yen-Yu Lin.  A complete characterization of unitary quantum space.  arXiv preprint arXiv:1604.01384, 2016.
  * [KSV02] A. Kitaev, A. Shen, and M. N. Vyalyi.  Classical and quantum computation.  American Mathematical Society, 2002.
  * [ZF87] Stathis Zachos and Martin Furer.  Probabilistic quantifiers vs. distrustful adversaries.  In International Conference on Foundations of Software Technology and Theoretical Computer Science, pages 443–455. Springer, 1987.