# Computing Longest Common Subsequence
under Cartesian-Tree Matching Model

Taketo Tsujimoto  Department of Information Science and Technology, Kyushu
University  Hiroki Shibata  College of Information Science, University of
Tsukuba  Takuya Mieno  Department of Computer and Network Engineering,
University of Electro-Communications  Yuto Nakashima  Department of
Informatics, Kyushu University  Shunsuke Inenaga  Department of Informatics,
Kyushu University

###### Abstract

Two strings of the same length are said to _Cartesian-tree match_ (_CT-match_)
if their Cartesian-trees are isomorphic [Park et al., TCS 2020]. Cartesian-
tree matching is a natural model that allows for capturing similarities of
numerical sequences. Oizumi et al. [CPM 2022] showed that subsequence pattern
matching under CT-matching model can be solved in polynomial time. This
current article follows and extends this line of research: We present the
first polynomial-time algorithm that finds the _longest common subsequence
under CT-matching_ of two given strings $S$ and $T$ of length $n$, in
$O(n^{6})$ time and $O(n^{4})$ space for general ordered alphabets. We then
show that the problem has a faster solution in the binary case, by presenting
an $O(n^{2}/\log n)$-time and space algorithm.

##  1 Introduction

The _longest common subsequence_ (_LCS_) is one of the most fundamental models
for measuring string similarities. It is well known that (the length of) an
LCS of two given strings $S$ and $T$ of length $n$ can be computed in
$O(n^{2})$ time and space by standard dynamic programming, or in $O(n^{2}/\log
n)$ time and space [13] by the so-called “Four-Russians” method in the word
RAM [3]. These quadratic and weakly sub-quadratic bounds are believed to be
essentially optimal, since a strongly sub-quadratic $O(n^{2-\epsilon})$-time
solution to LCS with any constant $\epsilon>0$ refutes the famous SETH [1, 5].
Indeed, while there are a number of algorithms for computing LCS whose running
times are dependent on other parameters (e.g. [10, 14, 2, 17]), their worst-
case time complexities remain $\Omega(n^{2})$.

The existing string alignments including LCS can be useful for natural
language text and biological sequences, however, these methods have
limitations in dealing with sequences for which non-exact matching models are
more suitable. For instance, in the analysis of numerical sequences such as
time series, capturing “structural” similarities is more important than simply
comparing them with standard alignments under the exact matching model.

_Order-preserving matching_ (_OP-matching_) is a natural model for dealing
with numerical sequences: Two strings $A$ and $B$ of length $n$ are said to be
OP-match iff the lexicographical rank of $A[i]$ in $A$ and that of $B[i]$ in
$B$ are equal for all $1\leq i\leq n$. While _substring_ matching is
polynomially solvable under OP-matching [11, 12, 6], it is known that
subsequence matching is NP-hard under OP-matching [4]. It is immediate from
the latter that _order-preserving longest common subsequence_ (_OP-LCS_) is
also NP-hard.

_Cartesian-tree matching_ (_CT-matching_), first proposed by Park et al. [16],
is another model for dealing with numerical sequences: Two strings $A$ and $B$
of length $n$ are said to be CT-match iff the (unlabeled) Cartesian trees [7]
of $A$ and $B$ are isomorphic. The CT-matching model is a relaxation of the
OP-matching model, i.e., any OP-matching strings also CT-match, but the
opposite is not true (for instance,
$A=\langle\mathtt{1},\mathtt{1},\mathtt{2}\rangle$ and
$B=\langle\mathtt{1},\mathtt{1},\mathtt{1}\rangle$ CT-match, but they do not
OP-match). CT-matching has attracted attention in terms of pattern matching
[16, 18], string periodicity [16], and indeterminate strings [8]. The recent
work by Oizumi et al. [15] has revealed that this relaxation enables us to
perform _subsequence_ matching under CT-matching in polynomial time: Given a
text $T$ of length $n$ and a pattern $P$ of length $m$, one can find all
minimal intervals $[i,j]$ in $T$ such that $T[i..j]$ contains a subsequence
$Q$ that CT-matches $P$ in $O(nm\log\log n)$ time and $O(n\log m)$ space.

The aforementioned result poses the natural question - Is the following _CT-
LCS problem_ also polynomial-time solvable?

######  Definition 1.1 (CT-LCS problem).

  * •

Input: Two strings $S$ and $T$ of length $n$.

  * •

Output: A pair $(P,Q)$ of longest strings $P$ and $Q$ such that $P$ is a
subsequence of $S$, $Q$ is a subsequence of $T$, and $P$ and $Q$ CT-match.

We answer this question affirmatively, by presenting an algorithm for
computing CT-LCS in $O(n^{6})$ time and $O(n^{4})$ space for general ordered
alphabets. We then present an $O(n^{2}/\log n)$-time and space algorithm for
computing CT-LCS in the case of binary alphabets. While the $O(n^{6})$-time
solution in the general case is based on the idea of _pivoted Cartesian-trees_
from Oizumi et al. [15], the $O(n^{2}/\log n)$-time solution for the binary
case is built on a completely different approach that exploits interesting
properties of CT-matching of binary strings.

##  2 Preliminaries

###  2.1 Strings

For any positive integer $i$, we define a set $[i]=\\{1,\ldots,i\\}$ of $i$
integers. Let $\Sigma$ be an _ordered alphabet_ of size $\sigma$. For
simplicity, let $\Sigma=\\{0,\ldots,\sigma-1\\}$. An element of $\Sigma$ is
called a _character_. A sequence of characters is called a _string_. The
_length_ of string $S$ is denoted by $|S|$. The empty string $\varepsilon$ is
the string of length $0$. If $S=XYZ$, then $X$, $Y$, and $Z$ are respectively
called a _prefix_ , _substring_ , and _suffix_ of $S$. For a string $S$,
$S[i]$ denotes the $i$th character of $S$ for each $i$ with $1\leq i\leq|S|$.
For each $i,j$ with $1\leq i\leq j\leq|S|$, $S[i..j]$ denotes the substring of
$S$ that begins at position $i$ and ends at position $j$. For convenience, let
$S[i..j]=\varepsilon$ for $i>j$. We write
$\mathsf{min}(S)=\min\\{S[i]\;|\;i\in[n]\\}$ for the minimum value contained
in the string $S$. For any $0\leq m\leq n$, let $\mathcal{I}_{m}^{n}$ be the
set consisting of all _subscript sequence_ $I=(i_{1},\ldots,i_{m})\in[n]^{m}$
in ascending order satisfying $1\leq i_{1}<\cdots<i_{m}\leq n$. For subscript
sequence $I=(i_{1},\ldots,i_{m})\in\mathcal{I}_{m}^{n}$, we denote by
$S_{I}=\langle S[i_{1}],\ldots,S[i_{m}]\rangle$ the _subsequence_ of $S$
corresponding to $I$. For a subscript sequence $I$ and its elements
$i_{s},i_{t}\in I$ with $i_{s}\leq i_{t}$, $I[i_{s}:i_{t}]$ denotes the
continuous subsequence of $I$ that starts with $i_{s}$ and ends with $i_{t}$.

###  2.2 Cartesian Tree Matching and CT-LCS

For a string $S$, let $\mathsf{min\\_id}(S)$ denote the least index $i$ such
that $S[i]$ is the smallest element in $S$. The _Cartesian tree_ of a string
$S$, denoted by $\mathsf{CT}(S)$, is the ordered binary tree recursively
defined as follows: If $S=\varepsilon$, then $\mathsf{CT}(S)$ is an empty
tree, and otherwise, $\mathsf{CT}(S)$ is the tree rooted at
$i=\mathsf{min\\_id}(S)$ such that the left subtree of $i$ is
$\mathsf{CT}(S[1..i-1])$ and the right subtree of $i$ is
$\mathsf{CT}(S[i+1..|S|])$. For two strings $S$ and $T$ of equal length, the
two Cartesian trees $\mathsf{CT}(S)$ and $\mathsf{CT}(T)$ are isomorphic if
they have the same tree topology as ordered trees [9]. We denote it by
$\mathsf{CT}(S)=\mathsf{CT}(T)$. We say that two strings $S$ and $T$ _CT-
match_ if $\mathsf{CT}(S)=\mathsf{CT}(T)$.

A string $Q$ is said to be a _CT-subsequence_ of a string $S$ if there is a
subsequence $P$ of $S$ such that $\mathsf{CT}(Q)=\mathsf{CT}(P)$. A string $Q$
is said to be a _common CT-subsequence_ of two strings $S$ and $T$ if $Q$ is a
CT subsequence of both $S$ and $T$. A string $Q$ is said to be a _longest
common CT-subsequence_ (_CT-LCS_) of $S$ and $T$ if there are no CT common
subsequences of $S$ and $T$ longer than $Q$. The length of CT-LCS of strings
$S$ and $T$ is denoted by $\mathsf{ct\\_lcs}(S,T)$. We show an example of CT-
LCS in Fig. 1

######  Problem 2.1.

Given two strings $S$ and $T$ of length $n$, compute $\mathsf{ct\\_lcs}(S,T)$.

Figure 1:
$Q=\langle\mathtt{5},\mathtt{3},\mathtt{14},\mathtt{2},\mathtt{11}\rangle$ is
a CT longest common subsequence of
$S=\langle\mathtt{12},\mathtt{5},\mathtt{3},\mathtt{14},\mathtt{2},\mathtt{9},\mathtt{4},\mathtt{11}\rangle$
and
$T=\langle\mathtt{3},\mathtt{2},\mathtt{5},\mathtt{9},\mathtt{7},\mathtt{12},\mathtt{8},\mathtt{1}\rangle$.
Each node in $\mathsf{CT}(Q)$ is labeled by the corresponding position in $Q$.

##  3 Algorithm for CT-LCS problem for general ordered alphabet

In this section, we propose an algorithm for solving CT-LCS problem for
general ordered alphabet. An $O(n^{6})$-time and $O(n^{4})$-space algorithm,
which is our main result will be given in Section 3.2. We start from
explaining an $O(n^{8})$-time and $O(n^{6})$-space algorithm for simplicity
(Section 3.1).

For each $c\in\Sigma$, let $P_{c}(S)=\\{i\mid S[i]=c\\}$ and let $S^{\prime}$
be the string of length $|S|$ such that $S^{\prime}[i]=(S[i],r_{i})$ for
$1\leq i\leq|S|$, where $r_{i}$ is the rank of $i$ in $P_{c}(S)$. For ordered
pairs $(c,r)$ and $(c^{\prime},r^{\prime})$ of characters and integers, let
$(c,r)<(c^{\prime},r^{\prime})$ iff (1) $c<c^{\prime}$ or (2) $c=c^{\prime}$
and $r<r^{\prime}$. Then, it holds that $\mathsf{CT}(S)$ and
$\mathsf{CT}(S^{\prime})$ are isomorphic. Thus, without loss of generality, we
can assume that all characters in the string $S$ are distinct. The same
assumption applies to the other string $T$, but $S$ and $T$ may share the same
characters.

###  3.1 $O(n^{8})$-time and $O(n^{6})$-space algorithm

We refer to a pair $(i,j)\in[n]^{2}$ of positions in $S$ and $T$ as a _pivot_.
Our algorithm in the general case is based on the idea of _pivoted Cartesian-
trees_ from Oizumi et al. [15] defined as follows.

######  Definition 3.1 (Fixed CT (longest) common subsequence).

Let $(i,j)\in[n]^{2}$ be a pivot of strings $S$ and $T$. A string $Q$ is said
to be a _fixed CT common subsequence_ (_f-CT-CS_) of $S$ and $T$ with pivot
$(i,j)$ if there exist subscript sequences $I,J\in\mathcal{I}_{|Q|}^{n}$ such
that

  * •

$\mathsf{CT}(Q)=\mathsf{CT}(S_{I})=\mathsf{CT}(T_{J})$,

  * •

$S[i]=\mathsf{min}(S_{I})$, and

  * •

$T[j]=\mathsf{min}(T_{J})$.

Moreover, a string $Q$ is said to be the _fixed CT longest common subsequence_
(_f-CT-LCS_) of $S$ and $T$ with pivot $(i,j)$ if there are no f-CT-CS with
pivot $(i,j)$ longer than $Q$ (see also Fig. 2).

Figure 2:  $Q=\langle\mathtt{2},\mathtt{1},\mathtt{4},\mathtt{3}\rangle$ is a
fixed CT longest common subsequence of
$S=\langle\mathtt{12},\mathtt{5},\mathtt{3},\mathtt{14},\mathtt{2},\mathtt{9},\mathtt{4},\mathtt{11}\rangle$
and
$T=\langle\mathtt{3},\mathtt{2},\mathtt{5},\mathtt{9},\mathtt{7},\mathtt{12},\mathtt{8},\mathtt{1}\rangle$
with pivot $(2,5)$.

Our solution is a dynamic programming based on the f-CT-LCS. We also consider
the f-CT-LCS for substrings of $S$ and $T$, and will use positions $i,j\in[n]$
of the input strings to indicate a pivot for substrings, namely, we say pivot
$(i,j)\in[n]^{2}$ of substrings $S^{\prime}=S[\ell_{1}..r_{1}]$ and
$T^{\prime}=T[\ell_{2}..r_{2}]$ instead of pivot
$(i-\ell_{1}+1,j-\ell_{2}+1)\in[r_{1}-\ell_{1}+1]\times[r_{2}-\ell_{2}+1]$ of
$S^{\prime}$ and $T^{\prime}$, where $\ell_{1}\leq i\leq r_{1}$, $\ell_{2}\leq
j\leq r_{2}$. Let $C(i,j,\ell_{1},r_{1},\ell_{2},r_{2})$ be the length of the
f-CT-LCS of substrings $S[\ell_{1}..r_{1}]$ and $T[\ell_{2}..r_{2}]$ with
pivot $(i,j)$. It is clear from the definition that

$\mathsf{ct\\_lcs}(S,T)=\max\\{C(i,j,1,n,1,n)\;|\;1\leq i\leq n,1\leq j\leq
n\\}$

holds. The following lemma shows the main idea of computing $C(i,j,1,n,1,n)$
by a dynamic programming (see also Fig. 3 for an illustration).

######  Lemma 3.2.

For any $(i,j,\ell_{1},r_{1},\ell_{2},r_{2})\in[n]^{6}$ that satisfies
$\ell_{1}\leq i\leq r_{1}$, $\ell_{2}\leq j\leq r_{2}$, we define
$\mathcal{M}_{L}$ and $\mathcal{M}_{R}$ as follows:

$\displaystyle\mathcal{M}_{L}=\\{$ $\displaystyle
C(i^{\prime},j^{\prime},\ell_{1},i-1,\ell_{2},j-1)$ $\displaystyle\mid
S[i^{\prime}]>S[i],T[j^{\prime}]>T[j],\ell_{1}\leq i^{\prime}\leq
i-1,\ell_{2}\leq j^{\prime}\leq j-1\\}\cup\\{0\\},$
$\displaystyle\mathcal{M}_{R}=\\{$ $\displaystyle
C(i^{\prime},j^{\prime},i+1,r_{1},j+1,r_{2})$ $\displaystyle\mid
S[i^{\prime}]>S[i],T[j^{\prime}]>T[j],i+1\leq i^{\prime}\leq r_{1},j+1\leq
j^{\prime}\leq r_{2}\\}\cup\\{0\\}.$

The following recurrence formula holds:

$C(i,j,\ell_{1},r_{1},\ell_{2},r_{2})=\max\mathcal{M}_{L}+\max\mathcal{M}_{R}+1.$

###### Proof.

Let $Q$ be the f-CT-LCS of $S[\ell_{1}..r_{1}]$ and $T[\ell_{2}..r_{2}]$ with
$(i,j)$. By Definition 3.1, there exist subscript sequences
$I=(i_{1},\ldots,i_{|Q|})$ and $J=(j_{1},\ldots,j_{|Q|})$ that satisfy
$\mathsf{CT}(Q)=\mathsf{CT}(S_{I})=\mathsf{CT}(T_{J})$. It is also clear from
the definition that $S[i]=\mathsf{min}(S_{I})$ and $T[j]=\mathsf{min}(T_{J})$
hold. Let $q=\mathsf{min\\_id}(Q)$. We show that $q-1=\max\mathcal{M}_{L}$
holds.

  * •

Assume that $q=1$. In this case, we need to show $\mathcal{M}_{L}=\\{0\\}$.
Suppose on the contrary that there exists $(i^{\prime},j^{\prime})$ such that
$S[i^{\prime}]>S[i]$, $T[j^{\prime}]>T[j]$, $\ell_{1}\leq i^{\prime}\leq i-1$,
and $\ell_{2}\leq j^{\prime}\leq j-1$. Let
$I^{*}=(i^{\prime},i_{1},\ldots,i_{|Q|})$,
$J^{*}=(j^{\prime},j_{1},\ldots,j_{|Q|})$, and $Q^{*}=\alpha\cdot Q$ where
$\alpha$ is a character in $\Sigma$ that satisfies $\alpha>Q[q]$. Also,
$\mathsf{CT}(Q^{*})=\mathsf{CT}(S_{I^{*}})=\mathsf{CT}(T_{J^{*}})$ holds since
$\mathsf{CT}(Q)=\mathsf{CT}(S_{I})=\mathsf{CT}(T_{J})$, $\alpha>Q[q]$,
$S[i^{\prime}]>S[i]$, and $T[j^{\prime}]>T[j]$ hold. Moreover, $Q^{*}$ is an
f-CT-CS of $S[\ell_{1}..r_{1}]$ and $T[\ell_{2}..r_{2}]$ with $(i,j)$, since
$S[i]=\mathsf{min}(S_{I^{*}})$ and $T[j]=\mathsf{min}(T_{J^{*}})$. This
contradicts to the fact that $Q$ is the f-CT-LCS of $S[\ell_{1}..r_{1}]$ and
$T[\ell_{2}..r_{2}]$ with $(i,j)$ (from $|Q^{*}|>|Q|$). Thus,
$\mathcal{M}_{L}=\\{0\\}$ and $\max\mathcal{M}_{L}=0$.

  * •

Assume that $q>1$. Let $p_{1}$ (resp., $p_{2}$) be the predecessor of $i$ in
$I$ (resp., the predecessor of $j$ in $J$). By the definition of the Cartesian
tree,
$\mathsf{CT}(Q[1..q-1])=\mathsf{CT}(S_{I[i_{1}:p_{1}]})=\mathsf{CT}(T_{J[j_{1}:p_{2}]})$
holds, and there exist $i^{*}$ and $j^{*}$ such that
$S[i^{*}]=\mathsf{min}(S_{I[i_{1}:p_{1}]})(>S[i])$ and
$T[j^{*}]=\mathsf{min}(T_{J[j_{1}:p_{2}]})(>T[j])$. This implies that
$Q[1..q-1]$ is an f-CT-CS of $S[\ell_{1}..i-1]$ and $T[\ell_{2}..j-1]$ with
$(i^{*},j^{*})$. Thus, $|Q[1..q-1]|=q-1\leq\max\mathcal{M}_{L}$ holds. In the
rest of this case, we show $q-1\geq\max\mathcal{M}_{L}$ to prove the equality.
Suppose on the contrary that $q-1<\max\mathcal{M}_{L}$. Since
$0<q-1<\max\mathcal{M}_{L}$ (from assumptions), there exists
$(i^{\prime\prime},j^{\prime\prime})\in[n]^{2}$ such that
$C(i^{\prime\prime},j^{\prime\prime},\ell_{1},i-1,\ell_{2},j-1)=\max\mathcal{M}_{L}$.
Let $Q^{\prime\prime}$ be an f-CT-LCS string of $S[\ell_{1}..i-1]$ and
$T[\ell_{2}..j-1]$ with $(i^{\prime\prime},j^{\prime\prime})$. Then there
exist subscript sequences $I^{\prime\prime}$ and $J^{\prime\prime}$ over
$\\{\ell_{1},\ldots,i-1\\}$ and $\\{\ell_{2},\ldots,j-1\\}$, respectively,
such that
$\mathsf{CT}(Q^{\prime\prime})=\mathsf{CT}(S_{I^{\prime\prime}})=\mathsf{CT}(T_{J^{\prime\prime}})$.
Let $\hat{I}$ denote the subscript sequence that is the concatenation of
$I^{\prime\prime}$ and $I[i:i_{|Q|}]$, and $\hat{J}$ denote the subscript
sequence that is the concatenation of $J^{\prime\prime}$ and $J[j:j_{|Q|}]$.
Then $\mathsf{CT}(Q^{\prime\prime}\cdot
Q[q..|Q|])=\mathsf{CT}(S_{\hat{I}})=\mathsf{CT}(T_{\hat{J}})$,
$S[i]=\mathsf{min}(S_{\hat{I}})$, and $T[j]=\mathsf{min}(T_{\hat{J}})$ hold.
This implies that $Q^{\prime\prime}\cdot Q[q..|Q|]$ is an f-CT-LCS of
$S[\ell_{1}..i-1]$ and $T[\ell_{2}..j-1]$ with $(i,j)$. However,
$|Q^{\prime\prime}\cdot
Q[q..|Q|]|=|Q^{\prime\prime}|+|Q[q..|Q|]|=\max\mathcal{M}_{L}+|Q|-q+1>q-1+|Q|-q+1=|Q|$
holds. This contradicts to the fact that $Q$ is the f-CT-LCS of
$S[\ell_{1}..i-1]$ and $T[\ell_{2}..j-1]$ with $(i,j)$.

Thus $q-1=\max\mathcal{M}_{L}$ also holds for $q>1$.

We can also prove $|Q|-q=\max\mathcal{M}_{R}$ by a symmetric manner.
Therefore, $|Q|=q-1+|Q|-q+1=\max\mathcal{M}_{L}+\max\mathcal{M}_{R}+1$ holds.
∎

Figure 3: Sketch of our recurrence by Lemma 3.2.

Then we can obtain an $O(n^{8})$-time and $O(n^{6})$-space algorithm for
solving the CT-LCS problem based on Lemma 3.2 (see Algorithm 1). Our algorithm
computes a six-dimensional table $C$ for any
$(i,j,\ell_{1},r_{1},\ell_{2},r_{2})\in[n]^{6}$ that satisfies $\ell_{1}\leq
i\leq r_{1}$, $\ell_{2}\leq j\leq r_{2}$. Notice that the processing order
$i_{1},i_{2},\ldots,i_{n}$ (resp., $j_{1},j_{2},\ldots,j_{n}$) w.r.t. index
$i$ (resp., $j$) has to satisfy $S[i_{1}]>S[i_{2}]>\cdots>S[i_{n}]$ (resp.,
$T[j_{1}]>T[j_{2}]>\cdots>T[j_{n}]$). The algorithm finally returns
$\mathsf{ct\\_lcs}(S,T)=\max\\{C(i,j,1,n,1,n)\mid 1\leq i\leq n,1\leq j\leq
n\\}$. For each fixed $(i,j,\ell_{1},r_{1},\ell_{2},r_{2})\in[n]^{6}$ (i.e.,
$O(n^{6})$ iterations), we can compute $\mathcal{M}_{L}$ and $\mathcal{M}_{R}$
in $O(n^{2})$ time. Therefore, we can compute table $C$ in $O(n^{8})$ time and
$O(n^{6})$ space.

######  Theorem 3.3.

The CT-LCS problem can be solved in $O(n^{8})$ time and $O(n^{6})$ space

Input: Strings $S[1..n],T[1..n]\in\Sigma^{*}$

Output: $\mathsf{ct\\_lcs}(S,T)$

1 Find $i_{1},i_{2},\ldots,i_{n}$ that satisfy
$S[i_{1}]>S[i_{2}]>\cdots>S[i_{n}]$;

2 Find $j_{1},j_{2},\ldots,j_{n}$ that satisfy
$T[j_{1}]>T[j_{2}]>\cdots>T[j_{n}]$;

3 $\mathit{ctlcs}\leftarrow 0$;

4 for  _$i\leftarrow i_{1}$ to $i_{n}$_ do

5 for  _$j\leftarrow j_{1}$ to $j_{n}$_ do

6 for  _$\ell_{1}\leftarrow 1$ to $i$_ do

7 for  _$r_{1}\leftarrow i$ to $n$_ do

8 for  _$\ell_{2}\leftarrow 1$ to $j$_ do

9 for  _$r_{2}\leftarrow j$ to $n$_ do

10 $\mathcal{M}_{L}\leftarrow 0$;

11 if  _$\ell_{1}\neq i$ and $\ell_{2}\neq j$_ then

12 for  _$i^{\prime}\leftarrow\ell_{1}$ to $i-1$_ do

13 for  _$j^{\prime}\leftarrow\ell_{2}$ to $j-1$_ do

14 if  _$S[i^{\prime}] >S[i]$ and $T[j^{\prime}]>T[j]$_ then

15
$\mathcal{M}_{L}\leftarrow\max(\mathcal{M}_{L},C[i^{\prime}][j^{\prime}][\ell_{1}][i-1][\ell_{2}][j-1])$;

16

17

18

19

20 $\mathcal{M}_{R}\leftarrow 0$;

21 if  _$r_{1}\neq i$ and $r_{2}\neq j$_ then

22 for  _$i^{\prime}\leftarrow i+1$ to $r_{1}$_ do

23 for  _$j^{\prime}\leftarrow j+1$ to $r_{2}$_ do

24 if  _$S[i^{\prime}] >S[i]$ and $T[j^{\prime}]>T[j]$_ then

25
$\mathcal{M}_{R}\leftarrow\max(\mathcal{M}_{R},C[i^{\prime}][j^{\prime}][i+1][r_{1}][j+1][r_{2}])$;

26

27

28

29

30
$C[i][j][\ell_{1}][r_{1}][\ell_{2}][r_{2}]\leftarrow\mathcal{M}_{L}+\mathcal{M}_{R}+1$;

31

32

33

34

35 $\mathit{ctlcs}\leftarrow\max(\mathit{ctlcs},C[i][j][1][n][1][n])$;

36

37

return _$\mathit{ctlcs}$_

Algorithm 1 Algorithm for solving CT-LCS problem

###  3.2 $O(n^{6})$-time $O(n^{4})$-space algorithm

In the rest of this section, we propose an improved algorithm based on the
previous algorithm. A new algorithm can solve the problem in $O(n^{6})$ time
and $O(n^{4})$ space. The key observation is that $\mathcal{M}_{L}$ and
$\mathcal{M}_{R}$ actually depend on only four variables. Namely,
$\mathcal{M}_{L}$ depends on $(i,j,\ell_{1},\ell_{2})$, and $\mathcal{M}_{R}$
depends on $(i,j,r_{1},r_{2})$. Let
$L(i,j,\ell_{1},\ell_{2})=\max\mathcal{M}_{L}$ and
$R(i,j,r_{1},r_{2})=\max\mathcal{M}_{R}$. Then we can represent
$C(i,j,\ell_{1},r_{1},\ell_{2},r_{2})$ as

$C(i,j,\ell_{1},r_{1},\ell_{2},r_{2})=L(i,j,\ell_{1},\ell_{2})+R(i,j,r_{1},r_{2})+1.$

Based on this recurrence formula, we can obtain the following alternative
lemma for an improvement.

######  Lemma 3.4.

For any $(i,j,\ell_{1},r_{1},\ell_{2},r_{2})\in[n]^{6}$ that satisfies
$\ell_{1}\leq i\leq r_{1}$, $\ell_{2}\leq j\leq r_{2}$, the following
recurrence formulae hold:

$\displaystyle L(i,j,\ell_{1},\ell_{2})=\max\\{$ $\displaystyle
L(i^{\prime},j^{\prime},\ell_{1},\ell_{2})+R(i^{\prime},j^{\prime},i-1,j-1)+1\mid
S[i^{\prime}]>S[i],$ $\displaystyle T[j^{\prime}]>T[j],\ell_{1}\leq
i^{\prime}\leq i-1,\ell_{2}\leq j^{\prime}\leq j-1\\}\cup\\{0\\},$
$\displaystyle R(i,j,r_{1},r_{2})=\max\\{$ $\displaystyle
L(i^{\prime},j^{\prime},i+1,j+1)+R(i^{\prime},j^{\prime},r_{1},r_{2})+1\mid
S[i^{\prime}]>S[i],$ $\displaystyle T[j^{\prime}]>T[j],\;i+1\leq
i^{\prime}\leq r_{1},\;j+1\leq j^{\prime}\leq r_{2}\\}\cup\\{0\\}.$

It is easy to see from definitions that

$\mathsf{ct\\_lcs}(S,T)=\max\\{L(i,j,1,1)+R(i,j,n,n)+1\ \mid 1\leq i\leq
n,1\leq j\leq n\\}$

holds.

Then we can obtain an $O(n^{6})$-time and $O(n^{4})$-space algorithm for
solving the CT-LCS problem based on Lemma 3.4 (see also Algorithm 2). Our
algorithm computes two dimensional tables $L$ and $R$. For each fixed
$(i,j)\in[n]^{2}$ (i.e., $O(n^{2})$ iterations), we can compute
$L(i,j,\cdot,\cdot)$ and $R(i,j,\cdot,\cdot)$ in $O(n^{4})$ time. The
algorithm finally returns
$\mathsf{ct\\_lcs}(S,T)=\max\\{L[i][j][1][1]+R[i][j][n][n]+1\mid 1\leq i\leq
n,1\leq j\leq n\\}$. Therefore, we can compute table $C$ in $O(n^{6})$ time
and $O(n^{4})$ space.

######  Theorem 3.5.

The CT-LCS problem can be solved in $O(n^{6})$ time and $O(n^{4})$ space.

Input: $S[1..n]$, $T[1..n]$

Output: $\mathsf{ct\\_lcs}(S,T)$

1 Find $i_{1},i_{2},\ldots,i_{n}$ that satisfy
$S[i_{1}]>S[i_{2}]>\cdots>S[i_{n}]$;

2 Find $j_{1},j_{2},\ldots,j_{n}$ that satisfy
$T[j_{1}]>T[j_{2}]>\cdots>T[j_{n}]$;

3 $\mathit{ctlcs}\leftarrow 0$;

4 for  _$i\leftarrow i_{1}$ to $i_{n}$_ do

5 for  _$j\leftarrow j_{1}$ to $j_{n}$_ do

6 for  _$\ell_{1}\leftarrow 1$ to $i$_ do

7 for  _$\ell_{2}\leftarrow i$ to $j$_ do

8 $L[i][j][\ell_{1}][\ell_{2}]\leftarrow 0$;

9 if  _$\ell_{1}\neq i$ and $\ell_{2}\neq j$_ then

10 for  _$i^{\prime}\leftarrow\ell_{1}$ to $i-1$_ do

11 for  _$j^{\prime}\leftarrow\ell_{2}$ to $j-1$_ do

12 if  _$S[i^{\prime}] >S[i]$ and $T[j^{\prime}]>T[j]$_ then

13 $L[i][j][\ell_{1}][\ell_{2}]$

$\leftarrow\max(L[i][j][\ell_{1}][\ell_{2}],L[i^{\prime}][j^{\prime}][\ell_{1}][\ell_{2}]+R[i^{\prime}][j^{\prime}][i-1][j-1]+1)$;

for  _$r_{1}\leftarrow i$ to $n$_ do

for  _$r_{2}\leftarrow j$ to $n$_ do

$R[i][j][r_{1}][r_{2}]\leftarrow 0$;

if  _$r_{1}\neq i$ and $r_{2}\neq j$_ then

for  _$i^{\prime}\leftarrow i+1$ to $r_{1}$_ do

for  _$j^{\prime}\leftarrow j+1$ to $r_{2}$_ do

if  _$S[i^{\prime}] >S[i]$ and $T[j^{\prime}]>T[j]$_ then

$R[i][j][r_{1}][r_{2}]$

$\leftarrow\max(R[i][j][r_{1}][r_{2}],L[i^{\prime}][j^{\prime}][i+1][j+1]+R[i^{\prime}][j^{\prime}][r_{1}][r_{2}]+1)$;

$\mathit{ctlcs}\leftarrow\max(\mathit{ctlcs},L[i][j][1][1]+R[i][j][n][n]+1)$;

return _$\mathit{ctlcs}$_

Algorithm 2 Faster algorithm for solving CT-LCS problem

We can compute a CT-LCS string if we store the following additional
information: We store pivot $(i^{\prime},j^{\prime})$ such that
$L[i][j][\ell_{1}][\ell_{2}]=L[i^{\prime}][j^{\prime}][\ell_{1}][\ell_{2}]+R[i^{\prime}][j^{\prime}][i-1][j-1]+1$
with $L(i,j,\ell_{1},\ell_{2})$ for any $(i,j,\ell_{1},\ell_{2})\in[n]^{4}$
that satisfies $\ell_{1}\leq i$, $\ell_{2}\leq j$ (also for $R$). If we do so,
we can compute a CT-LCS by tracking back the tables from the pivot $(i,j)$
that gives $\mathsf{ct\\_lcs}(S,T)$ in $O(|\mathsf{ct\\_lcs}(S,T)|)=O(n)$
time.

######  Corollary 3.6.

We can compute a CT-LCS string in $O(n^{6})$ time and $O(n^{4})$ space.

##  4 Algorithm for CT-LCS problem for binary alphabet

In this section, we propose an algorithm for solving CT-LCS problem for the
binary alphabet $\\{0,1\\}$. We assume that the strings $S$ and $T$ are binary
strings. In this section, we discard the assumption that all characters are
distinct in $S$ and in $T$. We first introduce the _parent-distance
representation_ presented by Park et al. [16]. We can decide by using the
representation whether two strings CT-match or not. Actually, we do not use
(compute) it in our algorithm, but we use it for explaining the correctness.

######  Definition 4.1 (Parent-distance representation [16]).

Given a string $S[1..n]$, the parent-distance representation of $S$ is an
integer string $\mathit{PD}(S)[1..n]$, which is defined as follows:

$\mathit{PD}(S)[i]=\left\\{\begin{aligned} &i-\max_{1\leq
j<i}\\{j\;|\;S[j]\leq S[i]\\}\quad&(\text{\rm{if such} }j\text{
\rm{exists}}),\\\ &0\quad&(\text{\rm{otherwise}}).\end{aligned}\right.$

######  Lemma 4.2 ([16]).

Two strings $S_{1}$ and $S_{2}$ CT-match if and only if $S_{1}$ and $S_{2}$
have the same parent-distance representations.

We start from a simple observation of CT-match for binary strings. Following
lemmas will support our algorithm for binary alphabet.

######  Lemma 4.3.

Let $S_{1}=1^{n}$ and $S_{2}$ be a binary string of length $n$. Then, $S_{1}$
and $S_{2}$ CT-match if and only if $S_{2}=0^{i}1^{n-i}$ for some integer
$i\geq 0$.

It is easy to see that $\mathit{PD}(1^{n})=01^{n-1}$. This implies that
$S_{2}$ should be a non-decreasing binary string. From here, we discuss the
case that $0$ appears in both $S_{1}$ and $S_{2}$.

######  Lemma 4.4.

For two binary strings $S_{1}$ and $S_{2}$ of length $n$ in which appears $0$,
$S_{1}$ and $S_{2}$ CT-match if and only if there exist a string $w$ and two
integers $i\geq 1$, $j\geq 1$ such that $S_{1}=w0^{i}1^{n-|w|-i}$ and
$S_{2}=w0^{j}1^{n-|w|-j}$.

###### Proof.

($\Longrightarrow$) Since $S_{1}$ and $S_{2}$ CT-match,
$\mathit{PD}(S_{1})=\mathit{PD}(S_{2})$ (from Theorem 4.2). Let $p$ (resp.,
$q$) be the smallest integer such that $S_{1}[p..n]=0^{i}1^{j}$ (resp.,
$S_{2}[q..n]=0^{i}1^{j}$) for some $i\geq 1$, $j\geq 0$. Assume that $1\leq
q<p$. Since $S_{1}[p-1]=1$ and $S_{1}[p]=0$, either $\mathit{PD}(S_{1})[p]=0$
or $\mathit{PD}(S_{1})[p]>1$ holds (i.e., $\mathit{PD}(S_{1})[p]\neq 1$). On
the other hand, $\mathit{PD}(S_{2})[p]=1$ holds since $S_{2}[p-1]\leq
S_{2}[p]$. Then $\mathit{PD}(S_{1})[p]\neq\mathit{PD}(S_{2})[p]$, which is a
contradiction. By a similar discussion, $1\leq p<q$ also leads a
contradiction. Next, we assume that $p=q=1$. This assumption implies that the
statement holds since $w=\varepsilon$. Assume that $1<p=q$. Suppose on the
contrary that $S_{1}[1..p-1]\neq S_{2}[1..p-1]$. There exists an integer
$j^{*}$ such that $j^{*}=\max_{1\leq j\leq p-1}\\{j\mid S_{1}[j]\neq
S_{2}[j]\\}$. This means that $S_{1}[j^{*}+1..p-1]=S_{2}[j^{*}+1..p-1]$. We
assume w.l.o.g. that $S_{1}[j^{*}]=0$ and $S_{2}[j^{*}]=1$.

  * •

If $0$ does not appear in $S_{1}[j^{*}+1..p-1]$,
$\mathit{PD}(S_{1})[p]=p-j^{*}>0$ holds. On the other hand, either
$\mathit{PD}(S_{2})[p]=0$ or $\mathit{PD}(S_{2})[p]>p-j^{*}$ holds. Thus
$\mathit{PD}(S_{1})\neq\mathit{PD}(S_{2})$, which is a contradiction.

  * •

If $0$ appears in $S_{1}[j^{*}+1..p-1]$, there exists an integer $i^{*}$ such
that $i^{*}=\min_{j^{*}+1\leq j\leq p-1}\\{j\mid S_{1}[j]=S_{2}[j]=0\\}$
holds. This implies that $\mathit{PD}(S_{1})[i^{*}]=i^{*}-j^{*}>0$ holds. On
the other hand, either $\mathit{PD}(S_{2})[i^{*}]=0$ or
$\mathit{PD}(S_{2})[i^{*}]>i^{*}-j^{*}$ holds. Thus
$\mathit{PD}(S_{1})\neq\mathit{PD}(S_{2})$, which is a contradiction.

Therefore, $S_{1}=w0^{i}1^{n-p+1-i}$ and $S_{2}=w0^{j}1^{n-p+1-j}$ hold for
some integers $i,j$ where $w=S_{1}[1..p-1]=S_{2}[1..p-1]$. ($\Longleftarrow$)
If $w=\varepsilon$, it is clear that $S_{1}$ and $S_{2}$ CT-match. We consider
the case of $w\neq\varepsilon$. We show, from Lemma 4.2, that
$\mathit{PD}(S_{1})=\mathit{PD}(S_{2})$ holds. It is easy to see that
$\mathit{PD}(S_{1})[i]=\mathit{PD}(S_{2})[i]$ for all $i$ that satisfies
$1\leq i\leq|w|$. Moreover, $\mathit{PD}(S_{1})[i]=\mathit{PD}(S_{2})[i]=1$
also holds for all $i$ with $|w|+1<i\leq n$. If $0$ does not appear in $w$,
$\mathit{PD}(S_{1})[|w|+1]=\mathit{PD}(S_{2})[|w|+1]=0$. We assume that $0$
appears in $w$ for the remaining case. Let $j^{*}=\max_{1\leq
j\leq|w|}\\{j\mid w[j]=0\\}$. Since $S_{1}[|w|+1]=S_{2}[|w|+1]=0$ and
$S_{1}[1..|w|]=S_{2}[1..|w|]$,
$\mathit{PD}(S_{1})[|w|+1]=\mathit{PD}(S_{2})[|w|+1]$ holds. Therefore
$\mathit{PD}(S_{1})=\mathit{PD}(S_{2})$. ∎

Based on the above two lemmas, we propose an algorithm for binary alphabet.
Let $N_{1}(S)$ be the number of occurrences of $1$ in string $S$, and
$L_{01}(S)$ the length of the longest non-decreasing subsequence of $S$. If
there is no such subsequence, let $L_{01}(S)=0$. We also define
$\mathsf{cand}(S,T)$ as the maximum integer
$k=|w|+i+j=|w|+i^{\prime}+j^{\prime}$ such that $w0^{i}1^{j}$ is a subsequence
of $S$ and $w0^{i^{\prime}}1^{j^{\prime}}$ is a subsequence of $T$ for some
string $w$, and integers $i,i^{\prime}\geq 1$, $j,j^{\prime}\geq 0$. Then the
following properties hold for subsequences $S^{\prime}$ and $T^{\prime}$ of
$S$ and $T$ that give $\mathsf{ct\\_lcs}(S,T)$.

  * •

If $0$ appears in both $S^{\prime}$ and $T^{\prime}$,
$\mathsf{ct\\_lcs}(S,T)=\mathsf{cand}(S,T)$ (from Lemma 4.4).

  * •

If either $S^{\prime}$ or $T^{\prime}$ does not have $0$,
$\mathsf{ct\\_lcs}(S,T)$ equals $\min(N_{1}(S),L_{01}(T))$ or
$\min(N_{1}(T),L_{01}(S))$, respectively (from Lemma 4.3).

  * •

If $0$ does not appears in both $S^{\prime}$ and $T^{\prime}$,
$\mathsf{ct\\_lcs}(S,T)=\min(N_{1}(S),N_{1}(T))$.

Due to the above properties,
$\mathsf{ct\\_lcs}(S,T)=\max(\mathsf{cand}(S,T),m_{1},m_{2},m_{3})$ holds for
$m_{1}=\min(N_{1}(S),L_{01}(T))$, $m_{2}=\min(N_{1}(T),L_{01}(S))$, and
$m_{3}=\min(N_{1}(S),N_{1}(T))$.

Now we explain our algorithm. Let $\mathit{LND}_{S}(i)=L_{01}(S[i..n])$ for
any integer $i$ with $1\leq i\leq n$. For convenience, let
$\mathit{LND}_{S}(n+1)=0$. Firstly, we compute $N_{1}(S[i..n])$,
$N_{1}(T[i..n])$, $\mathit{LND}_{S}(i)$, and $\mathit{LND}_{T}(i)$ for all $i$
that satisfies $1\leq i\leq n$. We can easily compute $N_{1}(S[i..n])$ and
$N_{1}(T[i..n])$ for all $i$ in $O(n)$ time and space. We can also compute
$\mathit{LND}_{S}(i)$ (and $\mathit{LND}_{T}(i)$ in a similar way) by using
the following recurrence formula:

$\mathit{LND}_{S}(i)=\left\\{\begin{aligned}
&\max(\mathit{LND}_{S}(i+1)+1,N_{1}(S[i+1..n])+1)\quad&(\text{if }S[i]=0)\\\
&\mathit{LND}_{S}(i+1)\quad&(\text{if }S[i]=1)\end{aligned}\right..$

These values can also be computed in $O(n)$ time and space.

Since values from $\mathsf{cand}$ require the length of $w$ which is described
in the above discussion, we use a data structure for computing the longest
common subsequence $\mathsf{LCS}(i,j)$ of $S[1..i]$ and $T[1..j]$. For
convenience, we set $\mathsf{LCS}(i,0)=\mathsf{LCS}(0,i)=0$ for all
$i\in[n]\cup\\{0\\}$. By using the Four-Russians method [13], we can compute
an $O(n^{2}/\log n)$-space data structure in $O(n^{2}/\log n)$ time that can
answer $\mathsf{LCS}(i,j)$ in $O(\log^{2}n)$ time for any $i\in[n]\cup\\{0\\}$
and $j\in[n]\cup\\{0\\}$. By the definition of $\mathsf{cand}$, the following
equation can be obtained:

$\mathsf{cand}(S,T)=\max_{1\leq\ell\leq
n}\\{\mathsf{LCS}(p_{\ell}-1,q_{\ell}-1)+\ell\\}$

where $p_{\ell}=\max\\{p\mid\mathit{LND}_{S}(p)=\ell\\}$ and
$q_{\ell}=\max\\{q\mid\mathit{LND}_{T}(q)=\ell\\}$ (see also Fig. 4 for an
illustration).

Figure 4: Illustration for our idea for computing $\mathsf{cand}(S,T)$.

Since we have already computed $\mathit{LND}_{S}(i)$, $\mathit{LND}_{S}(i)$,
and the data structure for $\mathsf{LCS}$, we can compute $\mathsf{cand}(S,T)$
in $O(n\log^{2}n)$ time based on the above equation. Finally, we can obtain
$\mathsf{ct\\_lcs}(S,T)$ by computing
$\max(\mathsf{cand}(S,T),m_{1},m_{2},m_{3})$ in constant time (see also
Algorithm 3).

Input: Binary strings $S[1..n],T[1..n]\in\\{0,1\\}^{*}$

Output: $\mathsf{ct\\_lcs}(S,T)$

Precompute data structure $\mathit{LCS}[i][j]$ that can answer
$\mathsf{LCS}(i,j)$ in $O(\log^{2}n)$ time for any $i\in[n]\cup\\{0\\}$ and
$j\in[n]\cup\\{0\\}$;

$N_{S}[n+1]\leftarrow 0$;

for  _$i\leftarrow n$ to $1$_ do

if  _$S[i]=0$_ then

$N_{S}[i]\leftarrow N_{S}[i+1]$;

else

$N_{S}[i]\leftarrow N_{S}[i+1]+1$;

$\mathit{LND}_{S}[n+1]\leftarrow 0$;

for  _$i\leftarrow n$ to $1$_ do

if  _$S[i]=0$_ then

$\mathit{LND}_{S}[i]\leftarrow\max(\mathit{LND}_{S}[i+1]+1,N_{S}[i+1]+1)$;

else

$\mathit{LND}_{S}[i]\leftarrow N_{S}[i+1]$;

$p[\ell]\leftarrow 0$ for all $\ell\in[n]$;

for  _$i\leftarrow 1$ to $n$_ do

$p[\mathit{LND}_{S}[i]]\leftarrow i$;

Compute $N_{T}[i]=N_{1}(T[i..n])$, $\mathit{LND}_{T}[i]=\mathit{LND}_{T}(i)$,
$q[\ell]=\max\\{q\;|\;\mathit{LND}_{T}[q]=\ell\\}$ for all $i\in[n+1]$ and
$\ell\in[n]$ in the same way;

$\mathit{cand}\leftarrow 0$;

for  _$\ell\leftarrow 1$ to $n$_ do

if  _$p[\ell]\neq 0$ and $q[\ell]\neq 0$_ then

$\mathit{cand}\leftarrow\max(\mathit{cand},\mathit{LCS}[p[\ell]-1][q[\ell]-1]+\ell)$;

$m_{1}\leftarrow\min(N_{S}[1],\mathit{LND}_{T}[1])$;

$m_{2}\leftarrow\min(\mathit{LND}_{S}[1],N_{T}[1])$;

$m_{3}\leftarrow\min(N_{S}[1],N_{T}[1])$;

return _$\max(\mathit{cand},m_{1},m_{2},m_{3})$_

Algorithm 3 Algorithm for solving CT-LCS problem on binary strings

######  Theorem 4.5.

The CT-LCS problem on binary can be solved in $O(n^{2}/\log n)$ time and
$O(n^{2}/\log n)$ space.

We can reconstruct a CT-LCS of $S$ and $T$ by using the information. If one of
$m_{1}$, $m_{2}$, and $m_{3}$ gives $\mathsf{ct\\_lcs}(S,T)$, we can easily
obtain a CT-LCS string in $O(n)$ time by using $\mathit{LND}_{S}(i)$ and
$\mathit{LND}_{T}(i)$. Otherwise, two subsequences $S^{\prime}$ and
$T^{\prime}$ which give $\mathsf{ct\\_lcs}(S,T)$ can be represented as
$S^{\prime}=w0^{i}1^{\ell-i}$ and $T^{\prime}=w0^{j}1^{\ell-j}$ for some $i$
and $j$. Integers $i$ and $j$ can be obtained by $\mathit{LND}_{S}(i)$ and
$\mathit{LND}_{T}(i)$. In the method of Four-Russians, $(n\times n)$-table
$\mathsf{LCS}$ is factorized into $(n/\log n\times n/\log n)$-blocks. The data
structure actually stores LCS values on boundaries of blocks. Thus we can
obtain string $w$ by tracing back in $O(n/\log n\cdot\log^{2}n)=O(n\log n)$
time (see also Fig. 5). Therefore, we can reconstruct a CT-LCS string in
$O(n\log n)$ time.

Figure 5: Illustration for an idea for reconstructing the LCS part.

######  Corollary 4.6.

We can also compute a CT-LCS string in $O(n^{2}/\log n)$ time and
$O(n^{2}/\log n)$ space.

## Acknowledgments

The authors thank Shay Mozes, Oren Weimann, and Tsubasa Oizumi for discussions
on subsequence CT-matching in the binary case.

This work was supported by JSPS KAKENHI Grant Numbers JP23H04381 (TM),
JP21K17705, JP23H04386 (YN), JP20H05964, JP22H03551 (SI).

## References

  * [1] A. Abboud, A. Backurs, and V. V. Williams.  Tight hardness results for LCS and other sequence similarity measures.  In FOCS 2015, pages 59–78, 2015.
  * [2] A. Apostolico, S. Browne, and C. Guerra.  Fast linear-space computations of longest common subsequences.  Theor. Comput. Sci., 92(1):3–17, 1992.
  * [3] V. Arlazarov, E. Dinic, M. Kronrod, and I. Faradzev.  On economical construction of the transitive closure of a directed graph.  Soviet Mathematics Doklady, 11(5):1209–1210, 1970.
  * [4] P. Bose, J. F. Buss, and A. Lubiw.  Pattern matching for permutations.  Inf. Process. Lett., 65(5):277–283, 1998.
  * [5] K. Bringmann and M. Künnemann.  Quadratic conditional lower bounds for string problems and dynamic time warping.  In FOCS 2015, pages 79–97, 2015.
  * [6] M. Crochemore, C. S. Iliopoulos, T. Kociumaka, M. Kubica, A. Langiu, S. P. Pissis, J. Radoszewski, W. Rytter, and T. Walen.  Order-preserving indexing.  Theor. Comput. Sci., 638:122–135, 2016.
  * [7] H. N. Gabow, J. L. Bentley, and R. E. Tarjan.  Scaling and related techniques for geometry problems.  In STOC 1984, pages 135–143, 1984.
  * [8] P. Gawrychowski, S. Ghazawi, and G. M. Landau.  On indeterminate strings matching.  In CPM 2020, volume 161 of LIPIcs, pages 14:1–14:14, 2020.
  * [9] C. M. Hoffmann and M. J. O’Donnell.  Pattern matching in trees.  J. ACM, 29(1):68–95, 1982.
  * [10] J. W. Hunt and T. G. Szymanski.  A fast algorithm for computing longest common subsequences.  Commun. ACM, 20(5):350–353, 1977.
  * [11] J. Kim, P. Eades, R. Fleischer, S. Hong, C. S. Iliopoulos, K. Park, S. J. Puglisi, and T. Tokuyama.  Order-preserving matching.  Theor. Comput. Sci., 525:68–79, 2014.
  * [12] M. Kubica, T. Kulczynski, J. Radoszewski, W. Rytter, and T. Walen.  A linear time algorithm for consecutive permutation pattern matching.  Inf. Process. Lett., 113(12):430–433, 2013.
  * [13] W. J. Masek and M. S. Paterson.  A faster algorithm computing string edit distances.  J. Comput. Syst. Sci., 20(1):18–31, 1980.
  * [14] N. Nakatsu, Y. Kambayashi, and S. Yajima.  A longest common subsequence algorithm suitable for similar text strings.  Acta Inf., 18:171–179, 1982.
  * [15] T. Oizumi, T. Kai, T. Mieno, S. Inenaga, and H. Arimura.  Cartesian tree subsequence matching.  In CPM 2022, volume 223 of LIPIcs, pages 14:1–14:18, 2022.
  * [16] S. G. Park, M. Bataa, A. Amir, G. M. Landau, and K. Park.  Finding patterns and periods in Cartesian tree matching.  Theor. Comput. Sci., 845:181–197, 2020.
  * [17] Y. Sakai.  Computing the longest common subsequence of two run-length encoded strings.  In ISAAC 2012, pages 197–206, 2012.
  * [18] S. Song, G. Gu, C. Ryu, S. Faro, T. Lecroq, and K. Park.  Fast algorithms for single and multiple pattern Cartesian tree matching.  Theor. Comput. Sci., 849:47–63, 2021.