Approximate Cartesian Tree Matching with Substitutions

Charalampopoulos, Panagiotis; Ellert, Jonas; Mohamed, Manal

doi:10.4230/LIPIcs.STACS.2026.26

Approximate Cartesian Tree Matching
with Substitutions

Panagiotis Charalampopoulos

King’s College London, UK Jonas Ellert

DIENS, École normale supérieure de Paris, PSL Research University, France Manal Mohamed

King’s College London, UK

Abstract

The Cartesian tree of a sequence captures the relative order of the sequence’s elements. In recent years, Cartesian tree matching has attracted considerable attention, particularly due to its applications in time series analysis. Consider a text $T$ of length $n$ and a pattern $P$ of length $m$ . In the exact Cartesian tree matching problem, the task is to find all length- $m$ fragments of $T$ whose Cartesian tree coincides with the Cartesian tree $\textsf{{CT}}(P)$ of the pattern. Although the exact version of the problem can be solved in linear time [Park et al., TCS 2020], it remains rather restrictive; for example, it is not robust to outliers in the pattern.

To overcome this limitation, we consider the approximate setting, where the goal is to identify all fragments of $T$ that are close to some string whose Cartesian tree matches $\textsf{{CT}}(P)$ . In this work, we quantify closeness via the widely used Hamming distance metric. For a given integer parameter $k>0$ , we present an algorithm that computes all fragments of $T$ that are at Hamming distance at most $k$ from a string whose Cartesian tree matches $\textsf{{CT}}(P)$ . Our algorithm runs in time $\mathcal{O}(n\sqrt{m}\cdot k^{2.5})$ for $k\leq m^{1/5}$ and in time $\mathcal{O}(nk^{5})$ for $k\geq m^{1/5}$ , thereby improving upon the state-of-the-art $\mathcal{O}(nmk)$ -time algorithm of Kim and Han [TCS 2025] in the regime $k=o(m^{1/4})$ .

On the way to our solution, we develop a toolbox of independent interest. First, we introduce a new notion of periodicity in Cartesian trees. Then, we lift multiple well-known combinatorial and algorithmic results for string matching and periodicity in strings to Cartesian tree matching and periodicity in Cartesian trees.

Keywords and phrases:

Cartesian tree, Hamming distance, approximate pattern matching

Funding:

Jonas Ellert: Partially funded by grant ANR20-CE48-0001 from the French National Research Agency.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Pattern matching

Related Version:

Full Version: https://arxiv.org/abs/2602.08570

Acknowledgements:

We thank the anonymous reviewers of STACS 2026 for their helpful feedback.

DOI:

10.4230/LIPIcs.STACS.2026.26

Event:

43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Editors:

Meena Mahajan, Florin Manea, Annabelle McIver, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Pattern matching is a central topic in theoretical computer science and a ubiquitous task in practical applications. In several real-world scenarios, such as stock price analysis and music analysis, one may wish to match a pattern with respect to the relative order between its sequential data points rather than their exact values. For instance, consider the challenge of matching the performance of a stock in the past quarter to its historical performance in order to predict its future behaviour. In this task, we are not concerned with the exact stock price but rather with its “ups and downs”. Several notions of matching have been devised for capturing such scenarios, including Cartesian tree matching [1, 20, 26, 28, 29, 31] and order-preserving pattern matching [5, 7, 8, 9, 13, 15, 17, 22, 25, 30]. Here, we focus on the Cartesian tree matching problem, which was introduced by Park et al. [29].

A Cartesian tree $\textsf{{CT}}(S)$ of a string $S$ is a binary tree defined recursively as follows: the root of the tree corresponds to the index $i$ of the minimum element in the sequence (under a fixed tie-breaking strategy); the left subtree of the root corresponds to the Cartesian tree of $S[1\mathinner{.\,.}i-1]$ , and the right subtree of the root corresponds to the Cartesian tree of $S[i+1\mathinner{.\,.}\lvert S\rvert]$ . In what follows, we assume that ties are always resolved in favour of the leftmost elements. The Cartesian tree of a string $S$ can be built in linear time [2].

We say that a string $U$ CT-matches a string $V$ if and only if $\textsf{{CT}}(U)=\textsf{{CT}}(V)$ . This notion of matching is well-behaved: it is a prime example of substring consistent equivalence relations [23] since, if $U$ and $V$ CT-match, then, for any $1\leq i\leq j\leq\lvert U\rvert$ , $U[i\mathinner{.\,.}j]$ and $V[i\mathinner{.\,.}j]$ CT-match as well [29].

In the Cartesian tree matching (CT-matching) problem, we are given a text $T$ of length $n$ and a pattern $P$ of length $m$ , and the goal is to compute all $m$ -length fragments of $T$ that CT-match $P$ . Park et al. [29] showed that this problem admits a linear-time solution. An alternative linear-time algorithm, as well as practical solutions, were later presented in [31]. Related problems such as dictionary CT-matching [29, 31] and indexing for CT-matching [20, 26, 28] have also been studied.

Approximate Cartesian tree matching.

Similarly to the case of standard string matching, requiring exact CT-matches can be quite restrictive. For instance, a single outlier value in the pattern (arising, for example, from an extreme but short-lived event or from noise in the data) may cause all relevant occurrences in the text to be missed. To address this, one can instead seek approximate CT-matches of $P$ in $T$ , that is, fragments of $T$ that are close to a string $X$ such that $\textsf{{CT}}(X)=\textsf{{CT}}(P)$ . Here, closeness may be measured in terms of some distance measure such as the Hamming distance or the edit distance. We consider the low distance regime, where an integer threshold parameter $k>0$ is provided. Then, we have to report fragments of $T$ at distance at most $k$ from a string $X$ with $\textsf{{CT}}(X)=\textsf{{CT}}(P)$ .

Auvray et al. [1] recently presented an $\mathcal{O}(nm)$ -time algorithm for the case of one difference (such as a swap or a substitution). Kim and Han [21] studied the problem of computing the edit and Hamming distances of two strings under CT-matching. They presented a dynamic-programming-based solution and, as corollaries, obtained an $\mathcal{O}(n^{3}mk)$ -time algorithm for approximate CT-matching under the edit distance and an $\mathcal{O}(nmk)$ -time algorithm for approximate CT-matching under the Hamming distance. In this work, we focus on approximate CT-matching under the Hamming distance.

Our contributions.

For equal-length strings $X$ and $Y$ , let $\textnormal{{CHd}}(X\leadsto Y)$ denote the minimum number of substitutions needed to transform $X$ into a string $X^{\prime}$ such that $\textsf{{CT}}(X^{\prime})=\textsf{{CT}}(Y)$ . We further define $\textnormal{{CHd}}_{k}(X\leadsto Y)=\min\{k+1,\textnormal{{CHd}}(X\leadsto Y)\}$ . We consider the following problem.

Approximate CT-Matching with Substitutions Input: A text $T$ of length $n$ , a pattern $P$ of length $m$ , and an integer threshold $k>0$ . Output: $\textnormal{{CHd}}_{k}(T[i\mathinner{.\,.}i+m)\leadsto P)$ for all $i\in[1,n-m+1]$ .

The state of the art solution of Kim and Han [21] computes $\textnormal{{CHd}}_{k}(T[i\mathinner{.\,.}i+m)\leadsto P)$ for each ${i\in[1,n-m+1]}$ separately in $\mathcal{O}(mk)$ time, resulting in $\mathcal{O}(nmk)$ overall time. In the spirit of a line of works in approximate string matching (see, e.g., [4, 6]), we show that this is not necessary by transferring the “few matches or almost periodicity” paradigm to approximate CT-matching. We obtain the following result.

Theorem 1.

The Approximate CT-Matching with Substitutions problem can be solved in $\mathcal{O}(n\sqrt{m}\cdot k^{2.5})$ time for $k\in[1,\lfloor m^{1/5}\rfloor]$ and in $\mathcal{O}(nk^{5})$ time for any $k\in[\lfloor m^{1/5}\rfloor,m]$ .

Hence, we improve upon the state of the art by polynomial factors when $k=\mathcal{O}(m^{1/4-\epsilon})$ for any constant $\epsilon>0$ . An illustration of the time complexities of our algorithm and the algorithm of Kim and Han [21] for the important case when $n=\Theta(m)$ is given in Figure 1. Along the way to proving Theorem 1, we develop a toolbox that we expect to find further applications in the study of Cartesian trees.

Figure 1: The running time

t(n,k)

of algorithms for Approximate CT-Matching with Substitutions as a function of

k

for the special case when

m=\Theta(n)

, shown on a doubly logarithmic scale.

Technical overview.

It is a folklore fact that a pattern $P$ of length $m$ is either periodic or it has at most one exact occurrence in a text $T$ of length $n\leq 3m/2$ [3]. In approximate string matching, recent algorithmic breakthroughs [4, 6] were obtained via analogous combinatorial results: either $P$ has few approximate occurrences in $T$ , or $P$ is almost periodic.

In the CT-matching model, it is not even clear what the right formalisation of periodicity is. Indeed, several notions of periodicity have been suggested and studied thus far [23, 29]. Here, we introduce a new notion of periodicity, namely CT-block-periodicity, that provides strong locality guarantees. We then exploit these guarantees to show that we either have few approximate CT-matches or the pattern is almost CT-block-periodic. Dealing with the almost CT-block-periodic case is the main technical challenge we overcome. The workhorse of our approach for this case is a combinatorial result (see Lemmas 31 and 34 for precise statements) that allows us to compute $\textnormal{{CHd}}_{k}(T[i\mathinner{.\,.}i+m)\leadsto P)$ very efficiently for almost all values of $i$ when $P$ is almost CT-block-periodic. Essentially, we prove (under some extra assumptions) that, for equal-length strings $X=X_{1}Q^{r}X_{2}$ and $Y=Y_{1}Q^{r}Y_{2}$ with $\lvert X_{1}\rvert=\lvert Y_{1}\rvert$ , the value of $\textnormal{{CHd}}_{k}(X\leadsto Y)$ is the same for all choices of $r\geq 2k+1$ .¹¹1We use $Q^{r}$ for simplicity in this overview, noting that standard string periodicity implies CT-block-periodicity. Lemmas 31 and 34 are more general. This allows us to trim aligned pairs of long CT-block-periodic fragments in $T[i\mathinner{.\,.}i+m)$ and $P$ , thus obtaining short strings $F$ and $P^{\prime}$ such that $\textnormal{{CHd}}_{k}(T[i\mathinner{.\,.}i+m)\leadsto P)=\textnormal{{CHd}}_{% k}(F\leadsto P^{\prime})$ , and compute the latter value in $\mathcal{O}(\lvert F\rvert\cdot k)$ time. In summary, in the case when the number of (candidate) approximate CT-matches may be large, the periodic structure allows us to verify almost all of them efficiently.

Other related work.

Cartesian trees have received significant attention in part due to their relation to the range minimum query problem [2, 10, 12]. Other problems that have been studied in the Cartesian tree matching model include computing the longest common subsequence [32], performing subsequence matching [27], computing palindromes [24], and matching indeterminate strings [14]. Other works on strings under substring consistent equivalence relations include [16, 18, 19].

2 Preliminaries

For integers $i,j\in\mathbb{Z}$ , we write $[i,j]=[i,j+1)=(i-1,j]=(i-1,j+1)$ to denote $\{h\in\mathbb{Z}\mid i\leq h\leq j\}$ . For a set $Z\subseteq\mathbb{Z}$ and an integer $y\in\mathbb{Z}$ , we define $Z-y=\{z-y:z\in Z\}$ .

A string $X$ of length $n=\lvert X\rvert$ is a finite sequence of $n$ characters over a finite alphabet $\Sigma$ . For $i,j\in[1,n]$ , the $i$ -th character of $X$ is denoted by $X[i]$ , and we use either of $X[i\mathinner{.\,.}j]$ , $X[i\mathinner{.\,.}j+1)$ , $X(i-1\mathinner{.\,.}j]$ , and $X(i-1\mathinner{.\,.}j+1)$ to denote the substring $X[i]X[i+1]\cdots X[j]$ of $X$ . If $i>j$ , then $X[i\mathinner{.\,.}j]$ is the empty string. We say that a string $Y$ has an occurrence at position $i$ of $X$ if $i+\lvert Y\rvert\leq\lvert X\rvert+1$ and $X[i\mathinner{.\,.}i+\lvert Y\rvert)=Y$ . We may refer to a substring $X[i\mathinner{.\,.}j]$ as a fragment if we want to emphasize that we mean the specific occurrence of $X[i\mathinner{.\,.}j]$ at position $i$ . Two fragments are disjoint if they do not share any positions.

An integer $p>0$ is a period of $X$ if $X[i]=X[i+p]$ for all $i\in[1,\lvert X\rvert-p]$ . The smallest period of $X$ is referred to as the period of $X$ and is denoted by $\textnormal{per}(X)$ . A run in $X$ is a fragment $Y=X[i\mathinner{.\,.}j]$ that satisfies $p:=\textnormal{per}(Y)\leq\lvert Y\rvert/2$ and is inclusion-maximal; that is, $X[i-1]\neq X[i-1+p]$ (or $i=1$ ) and $X[j+1]\neq X[j+1-p]$ (or $j=\lvert X\rvert$ ).

Lemma 2 (Periodicity Lemma (weak version) [11]).

If a string $S$ has periods $p$ and $q$ such that $p+q\leq\lvert S\rvert$ , then $\gcd(p,q)$ is also a period of $S$ .

Throughout the paper, we assume that the alphabet $\Sigma$ is totally ordered, and that an order comparison takes constant time. For a string $X$ , we define its leftmost minimum as the (positioned) character $X[j]$ , where $j=\min\{\,i\in[1,\lvert X\rvert]:X[i]=\min_{k\in[1,\lvert X\rvert]}X[k]\,\}$ . In other words, $j$ is the leftmost position at which the minimum character in $X$ occurs.

Cartesian Trees

In this work, consistent with the literature, we ensure that Cartesian trees are uniquely defined by resolving ties in favour of leftmost positions.

Definition 3.

The Cartesian tree of a string $X$ , denoted by $\textsf{{CT}}(X)$ , is a rooted ordered binary tree with $\lvert X\rvert$ nodes. The Cartesian tree of an empty string is the order-zero graph. For a non-empty string $X$ , $\textsf{{CT}}(X)$ is the tree obtained by creating a root node and (recursively) attaching to it $\textsf{{CT}}(X[1\mathinner{.\,.}j))$ as a left subtree and $\textsf{{CT}}(X(j\mathinner{.\,.}\lvert X\rvert])$ as a right subtree, where $X[j]$ is the leftmost minimum of $X$ .

Definition 4.

We say that a string $X$ CT-matches a string $Y$ (or that $X$ and $Y$ CT-match) if and only if $\textsf{{CT}}(X)=\textsf{{CT}}(Y)$ . We denote that two strings $X$ and $Y$ CT-match by writing $X\approx Y$ and that they do not CT-match by writing $X\not\approx Y$ .

Fact 5.

The CT-equivalence relation ( $\approx$ ) is a transitive relation. That is, for any three strings $X$ , $Y$ , and $Z$ , if $X\approx Y$ and $Y\approx Z$ , then $X\approx Z$ as well.

For strings $T[1\mathinner{.\,.}n]$ (the text) and $P[1\mathinner{.\,.}m]$ (the pattern), we say that $i\in[1,n-m+1]$ is a CT-occurrence of $P$ in $T$ (or that $P$ CT-occurs in $T$ at position $i$ ) if $P\approx T[i\mathinner{.\,.}i+\lvert P\rvert)$ . The CT-matching problem consists in computing all CT-occurrences of $P$ in $T$ .

Lemma 6 ([29]).

Given a text $T[1\mathinner{.\,.}n]$ and a pattern $P[1\mathinner{.\,.}m]$ , all CT-occurrences of $P$ in $T$ can be computed in $\mathcal{O}(n+m)$ time.

Lemma 7 ([29]).

Given a text $T[1\mathinner{.\,.}n]$ and patterns $P_{1}[1\mathinner{.\,.}m_{1}],\cdots,P_{h}[1\mathinner{.\,.}m_{h}]$ , all the CT-occurrences of all the patterns in $T$ can be computed in $\mathcal{O}((n+\sum_{i=1}^{h}m_{i})\log h)$ time.

For equal-length strings $X$ and $Y$ , $\textnormal{{CHd}}(X\leadsto Y)$ denotes the minimum number of substitutions needed to transform $X$ into a string $X^{\prime}$ such that $X^{\prime}\approx Y$ . We further define $\textnormal{{CHd}}_{k}(X\leadsto Y)=\min\{k+1,\textnormal{{CHd}}(X\leadsto Y)\}$ . Given a text $T[1\mathinner{.\,.}n]$ and a pattern $P[1\mathinner{.\,.}m]$ , we say that $P$ has a $k$ -approximate CT-occurrence at a position $i\in[1,n-m+1]$ of $T$ if $\textnormal{{CHd}}(T[i\mathinner{.\,.}i+m)\leadsto P)\leq k$ .

The following fact states that CT-matching is a substring consistent equivalence relation.

Fact 8 (Theorem 2, [29]).

For any strings $U$ and $V$ with $U\approx V$ , we have $U[i\mathinner{.\,.}j]\approx V[i\mathinner{.\,.}j]$ for all $i,j\in[1,\lvert U\rvert]$ .

There is a natural bijection between positions of a string $X$ and nodes in $\textsf{{CT}}(X)$ . We formalise this concept using the previous-smaller-or-equal-value function. For a string $X$ , we define

\displaystyle\textnormal{{psv}}_{X}:\quad

\displaystyle[1,\lvert X\rvert]\rightarrow[0,\lvert X\rvert),

\displaystyle i\mapsto\max(\{j\in[1,i)\mid X[j]\leq X[i]\}\cup\{0\}).

The parent-distance representation $\textnormal{{PD}}(X)$ of a string $X$ (see [29]) is a length- $\lvert X\rvert$ string with

\textnormal{{PD}}(X)[i]=\begin{cases}i-\textnormal{{psv}}_{X}(i)&\text{ if }% \textnormal{{psv}}_{X}(i)\neq 0;\\ 0&\text{otherwise.}\end{cases}

Intuitively, we have $\textnormal{{psv}}_{X}(i)=j$ if and only if the left subtree of the node corresponding to $X[i]$ in $\textsf{{CT}}(X)$ is $\textsf{{CT}}(X(j\mathinner{.\,.}i))$ . Given either of $\textnormal{{psv}}_{X}$ and $\textnormal{{PD}}(X)$ , one can (recursively) construct $\textsf{{CT}}(X)$ , and hence the following lemma holds.

Lemma 9 ([29, Theorem 1]).

For equal-length strings $X$ and $Y$ , $X\approx Y$ if and only if $\textnormal{{PD}}(X)=\textnormal{{PD}}(Y)$ , or equivalently $\forall i\in[1,\lvert X\rvert]:\textnormal{{psv}}_{X}(i)=\textnormal{{psv}}_{Y% }(i)$ .

We provide an example of a Cartesian tree $\textsf{{CT}}(X)$ , the function $\textnormal{{psv}}_{X}$ , the array $\textnormal{{PD}}(X)$ , and the distance function CHd in Figure 2.

Figure 2: The Cartesian tree

\textsf{{CT}}(X)

of

X=[4,5,6,1,2,7,7,8,3,9]

(top left), the tree induced by

\textnormal{{psv}}_{X}

(top right), and the values of

\textnormal{{psv}}_{X}

,

\textnormal{{nsv}}_{X}

,

\textnormal{{PD}}(X)

, and

\textnormal{{ND}}(X)

(bottom right). For

Y=[14,15,16,11,12,17,17,18,13,19]

, we have

X\approx Y

, illustrating that different sequences can yield the same Cartesian tree. In contrast, the Cartesian tree of

Z=[14,15,16,16,12,17,17,18,8,19]

(bottom left) is different, i.e., we have

Z\not\approx X

. However, we have

\textnormal{{CHd}}(X\leadsto Z)=2

because we can substitute the values of

X

at positions 4 and 9 to obtain

X^{\prime}=[4,5,6,\mathbf{6},2,7,7,8,\mathbf{1},9]\approx Z

.

For a string $X$ , analogously to $\textnormal{{psv}}_{X}$ , we define the next-smaller-value function, which captures the structure of the Cartesian tree as well:

\displaystyle\textnormal{{nsv}}_{X}:\quad

\displaystyle[1,\lvert X\rvert]\to[2,\lvert X\rvert+1],

\displaystyle i\mapsto\min\bigl(\{\,j\in(i,\lvert X\rvert]\mid X[j]<X[i]\,\}% \cup\{\lvert X\rvert+1\}\bigr).

We also define a length- $\lvert X\rvert$ string $\textnormal{{ND}}(X)$ by

\textnormal{{ND}}(X)[i]=\begin{cases}\textnormal{{nsv}}_{X}(i)-i,&\text{if }% \textnormal{{nsv}}_{X}(i)\neq\lvert X\rvert+1,\\ 0,&\text{otherwise}.\end{cases}

An analogue of Lemma 9 for $\textnormal{{nsv}}_{X}$ and $\textnormal{{ND}}(X)$ is provided in the full version.

3 Cartesian Periodicity

Several definitions of periodicity for strings with respect to Cartesian tree matching have been studied (see [23, 29]). Here, we use the following definitions.

Definition 10 ([23]).

A string $P[1\mathinner{.\,.}m]$ has a CT-border-period $p\in[1,m]$ if and only if $P[1\mathinner{.\,.}m-p]\approx P(p\mathinner{.\,.}m]$ .

Lemma 11.

The leftmost minimum of a string $P[1\mathinner{.\,.}m]$ with CT-border-period $p\in[1,\lfloor\frac{m}{2}\rfloor]$ lies outside $P(p\mathinner{.\,.}m-p]$ .

Proof.

Assume that $i\in(p,m-p]$ is the position of the leftmost minimum of $P$ . Then $P[i]$ is also the leftmost minimum of both $P[1\mathinner{.\,.}m-p]$ and $P(p\mathinner{.\,.}m]$ , and hence it is the root of both $\textsf{{CT}}(P[1\mathinner{.\,.}m-p])$ and $\textsf{{CT}}(P(p\mathinner{.\,.}m])$ . However, in this case, the left subtree under the root of $\textsf{{CT}}(P[1\mathinner{.\,.}m-p])$ is of size $i-1$ , while the the left subtree under the root of $\textsf{{CT}}(P(p\mathinner{.\,.}m])$ is of size $i-p-1$ . This contradicts the assumption that $P[1\mathinner{.\,.}m-p]\approx P(p\mathinner{.\,.}m]$ . $\hfill\blacktriangleleft$

Definition 12.

A string $P[1\mathinner{.\,.}m]$ has a CT-block-period $p\in[1,m]$ if and only if

$\blacksquare$

$p$ divides $m$ ,
$\blacksquare$

$p$ is a CT-border-period of $P$ , and
$\blacksquare$

the leftmost minimum of $P$ is either $P[1]$ or $P[m]$ .

$\blacktriangleright$ Remark 13.

The above definition restricts the definition of a full period from [29] by imposing the third condition. This condition crucially ensures that, for a CT-block-periodic fragment $X[i\mathinner{.\,.}j]$ of a string $X$ , either $\textnormal{{psv}}_{X}[k]\in[i,j)$ for all $k\in(i,j]$ or $\textnormal{{nsv}}_{X}[k]\in(i,j]$ for all $k\in[i,j)$ , thus providing locality guarantees.

Lemma 14.

Given $P[1\mathinner{.\,.}m]$ and a positive integer $p<m/3$ that is a CT-border-period of $P$ , we can compute a fragment of length at least $m-2p$ that has CT-block-period $p$ in $\mathcal{O}(p)$ time.

Proof.

Fact 8 implies that any substring of $P$ of length at least $p$ has CT-border-period $p$ . Let $m^{\prime}=p\cdot\lceil\frac{m}{p}\rceil-2p$ and note that $p<m-2p\leq m^{\prime}<m-p$ . By Lemma 11, there exists an offset $a\in[0,p)$ such that the leftmost minimum of $P$ is either $P[1+a]$ or $P[m-a]$ . If the leftmost minimum is $P[1+a]$ , then the fragment $P[1+a\mathinner{.\,.}m^{\prime}+a]$ has CT-block-period $p$ . Otherwise, the fragment $P(m-a-m^{\prime}\mathinner{.\,.}m-a]$ has CT-block-period $p$ . $\hfill\blacktriangleleft$

Lemma 15.

Consider a string $P[1\mathinner{.\,.}m]$ that has a CT-block-period $p\in[1,\lfloor\frac{m}{2}\rfloor)$ and such that $P[1]$ is the leftmost minimum of $P[1\mathinner{.\,.}m-p]$ . For $i\in[1,m/p]$ , let $c_{i}=(i-1)\cdot p+1$ . For all $i\in[1,m/p]$ , $P[c_{i}]$ is the leftmost minimum of $P[c_{i}\mathinner{.\,.}m]$ .

Proof.

For $i\in[1,m/p]$ denote $P_{i}:=P[c_{i}\mathinner{.\,.}m]$ . We prove by induction the more general statement that $p$ is a CT-block-period of $P_{i}$ for all $i$ with $P_{i}[1]$ being the leftmost minimum of $P_{i}$ . The induction hypothesis holds for $i=1$ since $P[1]$ is the leftmost minimum of $P[1\mathinner{.\,.}m-p]$ and is therefore smaller than $P[p+1]$ (since $p<m/2$ ), where $P[p+1]$ is the leftmost minimum of $P[p+1\mathinner{.\,.}m]$ . Now, consider any $i\in[2,m/p]$ and suppose that $p$ is a CT-block-period of $P_{i-1}$ with $P_{i-1}[1]$ being the leftmost minimum of $P_{i-1}$ . First, since $p$ is a CT-block-period of $P_{i-1}$ , we have $P_{i-1}[1\mathinner{.\,.}\lvert P_{i}\rvert]\approx P_{i}$ and hence the leftmost minimum of $P_{i}$ is $P_{i}[1]$ . Further, Fact 8 implies that

P[c_{i}\mathinner{.\,.}m-p]=P_{i-1}[1+p\mathinner{.\,.}\lvert P_{i-1}\rvert-p]% \approx P_{i-1}[1+2p\mathinner{.\,.}\lvert P_{i-1}\rvert]=P[c_{i}+p\mathinner{% .\,.}m]

and hence $p$ is a CT-border-period of $P_{i}$ . Finally, since $p$ divides $\lvert P\rvert$ , it also divides $\lvert P_{i}\rvert=\lvert P\rvert-(i-1)p$ . This completes the induction and the statement follows. $\hfill\blacktriangleleft$

An analogue of Lemma 15 for the case when $P[m]$ is the leftmost minimum of $P$ is given in the full version.

Fact 16.

Consider a string $X$ . The parent-distance representation of a fragment $X[i\mathinner{.\,.}j]$ of $X$ is given by, for $t\in[1,j-i+1]$ ,

\textnormal{{PD}}(X[i\mathinner{.\,.}j])[t]=\begin{cases}0,&\text{if }% \textnormal{{PD}}(X)[i+t-1]\geq t,\\[6.0pt] \textnormal{{PD}}(X)[i+t-1],&\text{otherwise}.\end{cases}

If $X[i]$ is a leftmost minimum of $X[i\mathinner{.\,.}j]$ , then $\textnormal{{PD}}(X)(i\mathinner{.\,.}j]$ is a suffix of $\textnormal{{PD}}(X[i\mathinner{.\,.}j])$ .

Lemma 17.

Consider a string $X$ and a fragment $X[i\mathinner{.\,.}j]$ with leftmost minimum $X[i]$ . Then, $p<j-i+1$ is a CT-block-period of $X[i\mathinner{.\,.}j]$ if and only if $p$ is a period of $\textnormal{{PD}}(X)(i\mathinner{.\,.}j]$ and $p$ divides $j-i+1$ .

Proof.

( $\Rightarrow$ :)

By the definition of a CT-block-period, we have that $p$ divides $j-i+1$ and that $X[i\mathinner{.\,.}j-p]\approx X[i+p\mathinner{.\,.}j]$ . By Lemma 9, this equality implies that

\textnormal{{PD}}(X[i\mathinner{.\,.}j-p])=\textnormal{{PD}}(X[i+p\mathinner{.% \,.}j]).

(1)

Further, by Fact 16, since $X[i]$ and $X[i+p]$ are the leftmost minima of $X[i\mathinner{.\,.}j-p]$ and $X[i+p\mathinner{.\,.}j]$ , respectively, we have that $\textnormal{{PD}}(X)(i\mathinner{.\,.}j-p]$ is a suffix of $\textnormal{{PD}}(X[i\mathinner{.\,.}j-p])$ and that $\textnormal{{PD}}(X)(i+p\mathinner{.\,.}j]$ is a suffix of $\textnormal{{PD}}(X[i+p\mathinner{.\,.}j])$ . By (1), we then have $\textnormal{{PD}}(X)(i\mathinner{.\,.}j-p]=\textnormal{{PD}}(X)(i+p\mathinner{% .\,.}j]$ and hence $p$ is a period of $\textnormal{{PD}}(X)(i\mathinner{.\,.}j]$ .

( $\Leftarrow$ :)

We first argue that it suffices to show that $X[i+p]$ is the leftmost minimum of $X[i+p\mathinner{.\,.}j]$ . If this is indeed the case, we have that $\textnormal{{PD}}(X)(i+p\mathinner{.\,.}j]=\textnormal{{PD}}(X)(i\mathinner{.% \,.}j-p]$ is a suffix of $\textnormal{{PD}}(X[i+p\mathinner{.\,.}j])$ which, together with the fact that $\textnormal{{PD}}(X[i\mathinner{.\,.}j-p])[1]=0=\textnormal{{PD}}(X[i+p% \mathinner{.\,.}j])[1]$ , implies that $\textnormal{{PD}}(X[i\mathinner{.\,.}j-p])=\textnormal{{PD}}(X[i+p\mathinner{.% \,.}j])$ and hence that $X[i\mathinner{.\,.}j-p]\approx X[i+p\mathinner{.\,.}j]$ by Lemma 9. Since $p$ divides $j-i+1$ and $X[i]$ is the leftmost minimum of $X[i\mathinner{.\,.}j]$ , $p$ is a CT-block-period of $X[i\mathinner{.\,.}j]$ .

Now, suppose for the sake of contradiction, that the leftmost minimum of $X[i+p\mathinner{.\,.}j]$ is at some position $z\in(i+p,j]$ . Then, $\textnormal{{psv}}_{X}(z)=z-\textnormal{{PD}}(X)[z]<i+p$ . Since $X[i]$ is the leftmost minimum of $X[i\mathinner{.\,.}j]$ , $\textnormal{{psv}}_{X}(z)\in[i,i+p)$ . Since $\textnormal{{PD}}(X(i\mathinner{.\,.}j])$ is periodic with period $p$ , we have $\textnormal{{PD}}(X)[z]=\textnormal{{PD}}(X)[z-p]$ . Therefore, our assumption implies that $\textnormal{{psv}}_{X}(z-p)=(z-p)-\textnormal{{PD}}(X)[z-p]=\textnormal{{psv}}% _{X}(z)-p<i$ , which contradicts the assumption that $X[i]$ is the leftmost minimum of $X[i\mathinner{.\,.}j]$ .

$\hfill\blacktriangleleft$

An analogue of the above lemma for the case when the leftmost minimum of $X[i\mathinner{.\,.}j]$ is $X[j]$ is given in the full version.

Corollary 18.

For equal-length strings $X$ and $Y$ that have a common CT-block-period $p\in[1,\lfloor\lvert X\rvert/2\rfloor]$ , we have $X\approx Y$ if and only if $X[1\mathinner{.\,.}2p]\approx Y[1\mathinner{.\,.}2p]$ .

Proof.

( $\Rightarrow$ :): This implication follows directly from Fact 8.
( $\Leftarrow$ :): Due to Lemma 15 and its analogue, both $X$ and $Y$ have their leftmost minima at the same position (since $X[1\mathinner{.\,.}2p]$ and $Y[1\mathinner{.\,.}2p]$ do). For the remainder of the proof, we assume that these minima occur at the first positions, noting that the remaining case can be handled symmetrically. Since $X[1\mathinner{.\,.}2p]\approx Y[1\mathinner{.\,.}2p]$ , Lemma 9 yields that $\textnormal{{PD}}(X[1\mathinner{.\,.}2p])=\textnormal{{PD}}(Y[1\mathinner{.\,.% }2p])$ . Further, we have $\textnormal{{PD}}(X[1\mathinner{.\,.}2p])=\textnormal{{PD}}(X)[1\mathinner{.\,% .}2p]$ and $\textnormal{{PD}}(Y[1\mathinner{.\,.}2p])=\textnormal{{PD}}(Y)[1\mathinner{.\,% .}2p]$ by Fact 16. Hence, $\textnormal{{PD}}(Y)[1\mathinner{.\,.}2p]=\textnormal{{PD}}(X)[1\mathinner{.\,% .}2p]$ . Since $p$ is a CT-block-period of each of $X$ and $Y$ , by applying Lemma 17 to each of $X$ and $Y$ , we conclude that $p$ is a period of both $\textnormal{{PD}}(X)(1\mathinner{.\,.}\lvert X\rvert]$ and $\textnormal{{PD}}(Y)(1\mathinner{.\,.}\lvert Y\rvert]$ . This directly implies that $\textnormal{{PD}}(X)=\textnormal{{PD}}(Y)$ , and we hence have $X\approx Y$ by Lemma 9.

$\hfill\blacktriangleleft$

Lemma 19.

Suppose that a fragment $X[i\mathinner{.\,.}j)$ has minimum CT-block-period $p$ . Then, for any $a,b\in[i,j]$ such that $a\equiv i\pmod{p}$ , $b\equiv j\pmod{p}$ , and $b-a\geq 2p$ , we have that $X[a\mathinner{.\,.}b)\approx X[i\mathinner{.\,.}i+(b-a))$ and that $X[a\mathinner{.\,.}b)$ has minimum CT-block-period $p$ .

Proof.

Without loss of generality, assume that $X[i]$ is the leftmost minimum of $X[i\mathinner{.\,.}j)$ . The complementary case when $X[j-1]$ is the leftmost minimum can be handled in a symmetric manner using the analogues of the lemmas used below.

Fix $a, b$ satisfying the conditions of the claim. If $a\neq i$ , then the CT-border-period $p$ of $X[i\mathinner{.\,.}j)$ implies that $X[a\mathinner{.\,.}b)\approx X[a-p\mathinner{.\,.}b-p)\approx\cdots\approx X[i% \mathinner{.\,.}i+(b-a)).$

Now, observe that $X[a]$ is the leftmost minimum of $X[a\mathinner{.\,.}j)$ by Lemma 15. Additionally, we have $X[a\mathinner{.\,.}b-p)\approx X[a+p\mathinner{.\,.}b)$ by Fact 8 because $p$ is a CT-border-period of $X[i\mathinner{.\,.}j)$ . Finally, $p$ divides $b-a$ by our assumptions and hence $p$ is a CT-block-period of $X[a\mathinner{.\,.}b)$ .

It remains to show that $p$ is the minimum CT-block-period of $X[a\mathinner{.\,.}b)$ . Towards a contradiction suppose that $X[a\mathinner{.\,.}b)$ has minimum CT-block-period $q<p$ . Then, by Lemma 17, $\textnormal{{PD}}(X)(a\mathinner{.\,.}b)$ has a period $q$ and $\textnormal{{PD}}(X)(i\mathinner{.\,.}j)$ has a period $p$ . Since the length of the fragment is $b-a\geq 2p>p+q$ , an application of the Periodicity Lemma (Lemma 2) yields that $\textnormal{{PD}}(X)(a\mathinner{.\,.}b)$ has period $\gcd(p,q)$ . Consequently, $\textnormal{{PD}}(X)(i\mathinner{.\,.}j)$ also has period $\gcd(p,q)$ . Another application of Lemma 17 implies that $X[i\mathinner{.\,.}j)$ has CT-block-period $\gcd(p,q)<p$ (since $\gcd(p,q)$ divides the length $j-i$ ), a contradiction. $\hfill\blacktriangleleft$

Definition 20.

Let $X$ be a string. A fragment $X[i\mathinner{.\,.}j]$ with minimum CT-block-period $p\leq(j-i+1)/2$ is called a CT-run if and only if $p$ is not a CT-block-period of $X[i-p\mathinner{.\,.}j]$ (or $i-p<1$ ) and $p$ is not a CT-block-period of $X[i\mathinner{.\,.}j+p]$ (or $j+p>\lvert X\rvert$ ).

The occurrences of a periodic pattern $P$ in a text $T$ form arithmetic progressions with each such progression corresponding to a run with period $\textnormal{per}(P)$ . We show an analogous result for CT-occurrences.

Example 21.

Consider a pattern $P=[10,40,30,20,60,50]$ . $P$ is of length $6$ and has a CT-block-period $p:=3$ . The leftmost minimum of $P$ is at its first position. The parent-distance array for $P$ is $\textnormal{{PD}}(P)=[0,1,2,3,1,2]$ .

Consider the text $T=[100,400,300,200,600,500,300,800,700,900]$ of length $n=10$ . The parent-distance array for $T$ is: $\textnormal{{PD}}(T)=[0,1,2,3,1,2,3,1,2,1]$ .

There are two CT-occurrences of $P$ in $T$ :

$\blacksquare$

at position $1$ , $T[1\mathinner{.\,.}6]=[100,400,300,200,600,500]$ , where $\textnormal{{PD}}(T[1\mathinner{.\,.}6])=[0,1,2,3,1,2]$ ;
$\blacksquare$

at position $4$ , $T[4\mathinner{.\,.}9]=[200,600,500,300,800,700]$ , where $\textnormal{{PD}}(T[4\mathinner{.\,.}9])=[0,1,2,3,1,2]$ .

Note that the fragment $T[1\mathinner{.\,.}9]$ forms a CT-run in $T$ with minimum CT-block-period $p=3$ .

Lemma 22.

Let $P$ be a pattern of length $m$ with minimum CT-block-period $p\leq m/4$ , and let $T$ be a text of length $n$ . The exact CT-occurrences of $P$ in $T$ can be partitioned into $\mathcal{O}(n/m)$ maximal arithmetic progressions with common difference $p$ . For each such progression $\{u+vp:v\in[0,z]\}$ , the fragment $T[u\mathinner{.\,.}u+zp+m)$ is a CT-run with minimum CT-block-period $p$ . For any two such arithmetic progressions $\{u_{1}+vp:v\in[0,z_{1}]\}$ and $\{u_{2}+vp:v\in[0,z_{2}]\}$ , the two runs $T[u_{1}\mathinner{.\,.}u_{1}+z_{1}p+m)$ and $T[u_{2}\mathinner{.\,.}u_{2}+z_{2}p+m)$ overlap by fewer than $p$ positions.

Proof.

We henceforth assume that the leftmost minimum of $P$ is at its first position. The proof for the complementary case, that is, when the leftmost minimum of $P$ is $P[m]$ , is symmetric (using ND instead of PD and the analogous versions of the used lemmas).

Let $P^{\prime}:=\textnormal{{PD}}(P)(1\mathinner{.\,.}m]$ . By the CT-block-periodicity of $P$ and Lemma 17 we have $\textnormal{per}(P^{\prime})=p$ . Since $P[1]$ is the leftmost minimum of $P$ , Fact 16 and 9 imply that $P$ CT-occurs at some position $x$ in $T$ if and only if the following two conditions hold:

$\blacksquare$

PD-match condition: $\textnormal{{PD}}(T)(x\mathinner{.\,.}x+m)=P^{\prime}$ ;
$\blacksquare$

left-min condition: $T[x]$ is the leftmost minimum of $T[x\mathinner{.\,.}x+m)$ .

Claim 23.

Consider a maximal arithmetic progression $D=\{j+ip:i\in[0,s]\}$ of occurrences of $P^{\prime}$ in $\textnormal{{PD}}(T)$ . For $i\in[0,s]$ , denote $d_{i}:=j+ip$ . Then, either $P$ does not have any CT-occurrence at a position of $T$ in $D-1$ , or there exists an integer $\mu\in[0,s]$ such that both of the following hold:

$\blacksquare$

the intersection of the set of CT-occurrences of $P$ in $T$ and $D-1$ is $\{d_{i}-1:i\in[\mu,s]\}$ ;
$\blacksquare$

$T[d_{\mu}-1\mathinner{.\,.}d_{s}-1+m)$ is a CT-run with minimum CT-block-period $p$ .

Proof.

By the definition of $D$ , we have $\textnormal{{PD}}(T)(x\mathinner{.\,.}x+m)=P^{\prime}$ for all $x\in D$ . Hence, the PD-match condition holds for all $x\in D-1$ . If the left-min condition fails for every element of $D-1$ , then $P$ does not have any CT-occurrence at any position of $T$ in $D-1$ , and the claim follows. Otherwise, let $\mu=\min\{i\in[0,s]:T[d_{i}-1]\mbox{ is a minimum in }T[{d_{i}-1}\mathinner{.% \,.}{d_{i}-1+m})\}$ . We show by induction that the left-min condition holds for all $x\in\{d_{i}-1:i\in[\mu,s]\}$ . The base case $y=\mu$ holds by definition. Assume that it holds for some $y\in[\mu,s)$ . An application of Lemma 15 to $T[d_{y}-1\mathinner{.\,.}d_{y+1}-1+m)$ implies that $T[d_{y+1}-1]$ is the leftmost minimum of $T[d_{y+1}-1\mathinner{.\,.}d_{y+1}-1+m)$ . This completes the proof of the inductive step and hence concludes the proof of the first item. Let $F:=T[d_{\mu}-1\mathinner{.\,.}d_{s}-1+m)$ . By repeatedly applying Lemma 15, we conclude that the leftmost minimum of $F$ is $F[1]$ , and hence that $p$ is a CT-block-period of $F$ . If $F$ had a smaller CT-block-period, then, by Lemma 19, the same would hold for $P$ , contradicting the assumption that $P$ has minimum CT-block-period $p$ . Finally, we cannot prepend or append $p$ characters to $F$ while maintaining that it has CT-block-period $p$ : either the obtained string does not have its leftmost minimum at its first position or we contradict the maximality of $D$ . This concludes the proof of the claim. $\hfill\vartriangleleft$

To complete the proof, it suffices to combine Claim 23 with the fact that a CT-occurrence of $P$ in $T$ at position $j$ implies an occurrence of $P^{\prime}$ in $\textnormal{{PD}}(T)$ at position $j+1$ , noting that the occurrences of $P^{\prime}$ in $\textnormal{{PD}}(T)$ can be partitioned into $\mathcal{O}(n/m)$ maximal arithmetic progressions with period $\textnormal{per}(P^{\prime})=p$ such that any two elements from distinct arithmetic progressions differ by more than $m-p$ (see [3, 11]). $\hfill\blacktriangleleft$

4 Approximate CT-Matching with Substitutions

Kim and Han [21] recently presented a dynamic programming algorithm that, given two strings $X$ and $Y$ , computes the minimum cost of a sequence of edit operations (insertions, deletions, and substitutions) required to transform $X$ into a string $X^{\prime}$ such that $X^{\prime}\approx Y$ . As noted in [21, Section 6], a minor modification to their algorithm results in the following lemma for the special case when only substitutions are allowed.

Lemma 24 (see [21]).

Given two strings $T[1\mathinner{.\,.}m]$ and $P[1\mathinner{.\,.}m]$ , and an integer threshold $k>0$ , we can compute $\textnormal{{CHd}}_{k}(T\leadsto P)$ in $\mathcal{O}(mk)$ time.

In the full version, we provide a self-contained proof of Lemma 24 for the sake of completeness.

4.1 Analysing the Pattern

Definition 25.

A set $\mathcal{S}$ of equal-length strings is a CT-rainbow if and only if there do not exist distinct $S_{1},S_{2}\in\mathcal{S}$ such that $S_{1}\approx S_{2}$ .

Lemma 26.

Let $m,\Delta\in\mathbb{Z}_{+}$ with $\Delta<\sqrt{m}/2$ . Given $\Delta$ and a string $P[1\mathinner{.\,.}m]$ , in $\mathcal{O}(m\Delta)$ time, we can either compute a set of $\Delta$ disjoint fragments of $P$ , each of length $\lceil m/{(2\Delta)}\rceil$ , that form a CT-rainbow or report a fragment of length at least $m/{(4\Delta)}$ that has a CT-block-period less than $\Delta$ , together with its minimal CT-block-period.

Proof.

Let $m^{\prime}=\lceil m/(2\Delta)\rceil$ . We process $P$ in a left-to-right manner, attempting to identify $m^{\prime}$ -length fragments to insert into an initially empty set $\mathcal{S}$ , which will remain a CT-rainbow throughout. Whenever a fragment is inserted into $\mathcal{S}$ , we find and mark all of its exact CT-occurrences in $P$ in $\mathcal{O}(m)$ time using Lemma 6. For each inserted fragment, we use a unique symbol for marking.

We first insert fragment $P[1\mathinner{.\,.}m^{\prime}]$ into $\mathcal{S}$ . Let $P[i\mathinner{.\,.}i+m^{\prime})$ be the fragment that was most recently inserted into $\mathcal{S}$ and assume that $\lvert\mathcal{S}\rvert<\Delta$ (otherwise, we return $\mathcal{S}$ and terminate the algorithm). Our goal is to then find some $j\in[i+m^{\prime}\mathinner{.\,.}i+m^{\prime}+\Delta)$ such that $P[j\mathinner{.\,.}j+m^{\prime})$ does not CT-match any element of $\mathcal{S}$ . To do this, it suffices to find, in $\mathcal{O}(\Delta)$ time, the first unmarked position in $[i+m^{\prime}\mathinner{.\,.}i+m^{\prime}+\Delta)$ , if one exists. If we can always find such a position $j$ while $\lvert\mathcal{S}\rvert<\Delta$ , then we eventually insert $\Delta$ fragments into $\mathcal{S}$ . This holds because the total length of the fragments inserted into $\mathcal{S}$ and the lengths of the gaps between them add up to at most $\Delta\cdot(m^{\prime}+\Delta-1)\leq{m/2}+\Delta^{2}\leq m$ since the length of the gap between any two consecutive fragments is less than $\Delta$ and $\Delta<\sqrt{m}/2$ . Inserting a fragment into $\mathcal{S}$ and marking all of its exact CT-occurrences takes $\mathcal{O}(m)$ time. In the case when we can always find a fragment to insert into $\mathcal{S}$ , the algorithm thus runs in $\mathcal{O}(m\Delta)$ time.

Now consider the complementary case when, after inserting some fragment $P[i\mathinner{.\,.}i+m^{\prime})$ into $\mathcal{S}$ , we have $\lvert\mathcal{S}\rvert<\Delta$ and all positions in $[i+m^{\prime}\mathinner{.\,.}i+m^{\prime}+\Delta)$ are marked. Then, by the pigeonhole principle, some fragment in $\mathcal{S}$ has two CT-occurrences at positions $i_{1}<i_{2}$ in $[i+m^{\prime}\mathinner{.\,.}i+m^{\prime}+\Delta)$ with $q:=i_{2}-i_{1}<\Delta$ . We find two such positions (marked with the same symbol) naively in $\mathcal{O}(\Delta^{2})\subseteq\mathcal{O}(m)$ time. Let $G=P[i_{1}\mathinner{.\,.}i_{2}+m^{\prime})$ . $G$ has length $L=m^{\prime}+q$ and CT-border-period $q$ . We apply Lemma 14 to trim $G$ . Both conditions of the lemma are satisfied since $\Delta>q$ , $m^{\prime}\geq m/(2\Delta)$ , and $\Delta<\sqrt{m}/2$ , and hence

L=m^{\prime}+q\geq m/(2\Delta)+q>\sqrt{m}+q\geq 2\Delta+q>3q.

Trimming $G$ yields a fragment $F$ with CT-block-period $q$ and length

\lvert F\rvert\geq L-2q=m^{\prime}-q\geq{m/(2\Delta)}-\Delta>{m/(2\Delta)}-% \sqrt{m}/2\geq m/(4\Delta).

Finally, we naively compute the smallest CT-block-period $p$ of $F$ by checking each integer in $[1,q-1]$ in $\mathcal{O}(m)$ time, for a total running time of $\mathcal{O}(m\Delta)$ , and return the pair $(F,p)$ . $\hfill\blacktriangleleft$

4.2 The Aperiodic Case

In this section, we deal with the (easy) case when the analysis of the pattern according to Lemma 26 returns a large CT-rainbow of disjoint fragments. We apply a standard marking trick: an exact CT-occurrence of a fragment $P[a\mathinner{.\,.}b]\in\mathcal{S}$ at a position $j$ in $T$ contributes a mark to position $j-a+1$ , indicating a potential starting position of a $k$ -approximate CT-occurrence of $P$ in $T$ . The following simple fact captures the key property we use: if ${\textnormal{{CHd}}_{k}(T[i\mathinner{.\,.}i+m)\leadsto P)\leq k}$ , then position $i$ must receive at least $\Delta-k$ marks.

Lemma 27.

Let $k,\Delta\in\mathbb{Z}_{+}$ with $\Delta\geq k$ . Consider strings $V, U$ satisfying ${\textnormal{{CHd}}_{k}(V\leadsto U)\leq k}$ . Let $\mathcal{U}=\{U[a_{i}\mathinner{.\,.}b_{i}]:i\in[1,\Delta]\}$ be a set of disjoint fragments of $U$ . Then there exists a set $I\subseteq[1,\Delta]$ of size at least $\Delta-k$ such that $V[a_{i}\mathinner{.\,.}b_{i}]\approx U[a_{i}\mathinner{.\,.}b_{i}]$ for all $i\in I$ .

Proof.

Let $V^{\prime}$ be a string obtained from $V$ by substituting at most $k$ characters such that $V^{\prime}\approx U$ . Let $I:=\{i\in[1,\Delta]:V[a_{i}\mathinner{.\,.}b_{i}]=V^{\prime}[a_{i}\mathinner{.% \,.}b_{i}]\}$ . Set $I$ is of size at least $\Delta-k$ as the substitutions transforming $V$ into $V^{\prime}$ affect at most $k$ fragments $V[a_{i}\mathinner{.\,.}b_{i}]$ . For each $i\in I$ , Fact 8 implies that $V^{\prime}[a_{i}\mathinner{.\,.}b_{i}]\approx U[a_{i}\mathinner{.\,.}b_{i}]$ . Moreover, for each $i\in I$ , we have $V[a_{i}\mathinner{.\,.}b_{i}]=V^{\prime}[a_{i}\mathinner{.\,.}b_{i}]$ and hence the claim follows. $\hfill\blacktriangleleft$

In the following lemma, we use the marking trick to efficiently compute a small number of candidate positions that need to be verified, and verify them using Lemma 24.

Lemma 28.

Let $n,m,k,\Delta\in\mathbb{Z}_{+}$ with $n\leq 3m/2$ and $2k\leq\Delta\leq\sqrt{m}/2$ . Given $k$ , a text $T[1\mathinner{.\,.}n]$ , and a pattern $P[1\mathinner{.\,.}m]$ , together with a CT-rainbow $\mathcal{P}$ consisting of $\Delta$ disjoint fragments of $P$ , each of length $\lceil m/{2\Delta}\rceil$ , we can compute $\textnormal{{CHd}}_{k}(T[i\mathinner{.\,.}i+m)\leadsto P)$ for all $i\in[1,n-m+1]$ in $\mathcal{O}(m^{2}k/\Delta)$ time.

Proof.

We perform multiple-pattern CT-matching in $T$ for all fragments of $\mathcal{P}$ in $\mathcal{O}(m\log m)\subset\mathcal{O}(m^{2}k/\Delta)$ time using Lemma 7. If a fragment $P[a\mathinner{.\,.}b]\in\mathcal{P}$ CT-matches a fragment $T[i\mathinner{.\,.}j]$ , we add a mark at position $i-a+1$ of $T$ . By the fact that $\mathcal{P}$ is a CT-rainbow and transitivity (Fact 5), at most one fragment of $\mathcal{P}$ can CT-match at any position of $T$ . Hence, the total number of marks is $\mathcal{O}(m)$ . Furthermore, Lemma 27 implies that if $\textnormal{{CHd}}_{k}(T[i\mathinner{.\,.}i+m)\leadsto P)\leq k$ , then position $i$ must receive at least $\Delta-k\geq\Delta/2$ marks. There are $\mathcal{O}(m/\Delta)$ such positions, which can be identified at no additional cost during the marking process. Each of these positions is then verified in $\mathcal{O}(mk)$ time using Lemma 24, yielding a total verification time of $\mathcal{O}(mk\cdot m/\Delta)=\mathcal{O}(m^{2}k/\Delta)$ . $\hfill\blacktriangleleft$

4.3 The Periodic Case

In this section, we address the (much more complicated) case when the analysis of the pattern according to Lemma 26 returns a long fragment with a small CT-block-period.

We first establish combinatorial lemmas that allow us to trim both $P$ and $T[i\mathinner{.\,.}i+m)$ under certain conditions before applying Lemma 24. Intuitively, whenever a long CT-block-periodic fragment of $T$ is aligned with a corresponding periodic fragment of $P$ , substitutions are not required in (a long part of) this fragment. This trimming improves computational efficiency, as the complexity of Lemma 24 depends on the lengths of the input strings.

Figure 3: An illustration of the settings in Lemmas 29 and 31 with

k=3

. The

\textnormal{{psv}}_{Y}

array is shown with grey arrows below string

Y

. Lemma 29 establishes that any sequence of

\textnormal{{CHd}}(X\leadsto Y)

substitutions that transforms

X

into

X^{\prime}

such that

{X^{\prime}\approx Y}

does not modify the fragment highlighted in red; the condition “

\forall i\in[c_{r}+p,\lvert Y\rvert]:\textnormal{{psv}}_{Y}(i)\notin[c_{1},c_{% r})

” ensures that none of these substitutions “interact” with this fragment. Lemma 31 establishes that we can trim a pair of fragments (one in

X

and one in

Y

) without altering the value of

\textnormal{{CHd}}(X\leadsto Y)

.

Lemma 29.

Consider $p,r,k\in\mathbb{Z}_{+}$ and strings $X=X_{1}UX_{2}$ and $Y=Y_{1}VY_{2}$ such that all of the following hold:

$\blacksquare$

$\lvert X_{1}\rvert=\lvert Y_{1}\rvert$ , $\lvert X_{2}\rvert=\lvert Y_{2}\rvert$ , and $\lvert U\rvert=\lvert V\rvert=rp$ , where $r\geq 2k+1$ ;
$\blacksquare$

$U\approx V$ ;
$\blacksquare$

there is no position $i\in[\lvert Y_{1}V\rvert+1\mathinner{.\,.}\lvert Y\rvert]$ such that $\textnormal{{psv}}_{Y}(i)\in[\lvert Y_{1}\rvert+1\mathinner{.\,.}\lvert Y_{1}V% \rvert-p]$ ;
$\blacksquare$

if we define $\forall i\in[1,r]:c_{i}:=\lvert X_{1}\rvert+(i-1)p+1$ , then $X[c_{i}]$ is a minimum in $X[c_{i}\mathinner{.\,.}c_{r}+p)$ , and $Y[c_{i}]$ is a minimum in $Y[c_{i}\mathinner{.\,.}c_{r}+p)$ ;
$\blacksquare$

$\textnormal{{CHd}}(X\leadsto Y)\leq k$ .

Any sequence of $\textnormal{{CHd}}(X\leadsto Y)$ substitutions that transforms $X$ into $X^{\prime}$ with $X^{\prime}\approx Y$ does not perform any substitution in fragment $X[c_{k+1}\mathinner{.\,.}c_{r-k}]$ .

Proof.

Consider any sequence of $\textnormal{{CHd}}(X\leadsto Y)$ substitutions that transforms $X$ into $X^{\prime}$ such that ${X^{\prime}\approx Y}$ . We fix $i,j\in[1,r]$ to be the minimal and maximal values, respectively, such that $X[c_{i}]$ and $X[c_{j}]$ are not modified. (There are at least two distinct values because $r\geq\textnormal{{CHd}}(X\leadsto Y)+2$ .) We show that no substitution is performed in $X[c_{i}\mathinner{.\,.}c_{j}]$ .

Let $Z=X^{\prime}[1\mathinner{.\,.}c_{i})\cdot X[c_{i}\mathinner{.\,.}c_{j}]\cdot X% ^{\prime}(c_{j}\mathinner{.\,.}\lvert X\rvert]=X^{\prime}[1\mathinner{.\,.}c_{% i}]\cdot X(c_{i}\mathinner{.\,.}c_{j})\cdot X^{\prime}[c_{j}\mathinner{.\,.}% \lvert X\rvert]$ . We claim that $Z\approx Y$ . If not, there would exist $x\in[1,\lvert X\rvert]$ with $\textnormal{{psv}}_{Z}(x)\neq\textnormal{{psv}}_{Y}(x)$ . We show that such $x$ does not exist by distinguishing between the following four cases:

Case 1:

$x\in[1,c_{i}]$ . Since $Z$ has prefix $X^{\prime}[1\mathinner{.\,.}c_{i}]$ , and due to $X^{\prime}\approx Y$ , Fact 8, and Lemma 9, we have $\forall x\in[1,c_{i}]:\textnormal{{psv}}_{Z}(x)=\textnormal{{psv}}_{X^{\prime}% }(x)=\textnormal{{psv}}_{Y}(x)$ .

Case 2:

$x\in(c_{i},c_{j}]$ . $Y[c_{i}]$ is minimal in $Y[c_{i}\mathinner{.\,.}c_{r}]$ by assumptions. Hence, $\textnormal{{psv}}_{Y}(x)\geq c_{i}$ . We obtain $\textnormal{{psv}}_{Z}(x)=\textnormal{{psv}}_{Y}(x)$ due to Lemma 9 and the observation that:

Z[c_{i}\mathinner{.\,.}c_{j}]=X[c_{i}\mathinner{.\,.}c_{j}]={}U(ip-p\mathinner% {.\,.}jp-p+1]{}\approx{}V(ip-p\mathinner{.\,.}jp-p+1]=Y[c_{i}\mathinner{.\,.}c% _{j}].

Case 3:

$x\in(c_{j},c_{r}+p)$ . Since $Y[c_{j}]$ is minimal in $Y[c_{j}\mathinner{.\,.}c_{r}+p)$ , we have $\textnormal{{psv}}_{Y}(x)\geq c_{j}$ . Therefore, $\textnormal{{psv}}_{Z}(x)=\textnormal{{psv}}_{X^{\prime}}(x)=\textnormal{{psv}% }_{Y}(x)$ follows from $Z[c_{j}\mathinner{.\,.}c_{r}+p)=X^{\prime}[c_{j}\mathinner{.\,.}c_{r}+p)% \approx Y[c_{j}\mathinner{.\,.}c_{r}+p)$ .

Case 4:

$x\in[c_{r}+p,\lvert X\rvert]$ . By the assumptions, we have $\textnormal{{psv}}_{Y}(x)\notin[\lvert Y_{1}\rvert+1,\lvert Y_{1}V\rvert-p]=[c% _{1},c_{r})$ . First, consider the case when $\textnormal{{psv}}_{Y}(x)\geq c_{r}$ . Note that $c_{j}\leq c_{r}$ implies $Z[c_{r}\mathinner{.\,.}\lvert X\rvert]=X^{\prime}[c_{r}\mathinner{.\,.}\lvert X\rvert]$ . Hence, $\textnormal{{psv}}_{Z}(x)=\textnormal{{psv}}_{X^{\prime}}(x)=\textnormal{{psv}% }_{Y}(x)$ follows from $X^{\prime}\approx Y$ , together with Fact 8 and 9. If, however, $\textnormal{{psv}}_{X^{\prime}}(x)=\textnormal{{psv}}_{Y}(x)<c_{1}\leq c_{i}$ , then clearly $X^{\prime}[x]<X^{\prime}[c_{i}]=X[c_{i}]$ . Since $X[c_{i}]=Z[c_{i}]$ is minimal in $X[c_{i}\mathinner{.\,.}c_{j})=Z[c_{i}\mathinner{.\,.}c_{j})$ , it cannot be that $\textnormal{{psv}}_{Z}(x)\in[c_{i},c_{j})$ , which implies $\textnormal{{psv}}_{Z}(x)=\textnormal{{psv}}_{X^{\prime}}(x)=\textnormal{{psv}% }_{Y}(x)$ .

We have shown that $Z\approx Y$ . Hence, the considered sequence of substitutions did not modify $X[c_{i}\mathinner{.\,.}c_{j}]$ . Finally, by the definition of $i$ and $j$ , the characters in positions $c_{1},\dots,c_{i-1}$ and $c_{j+1},\dots,c_{r}$ in $X$ must have been modified. We therefore have $(i-1)+(r-j)\leq\textnormal{{CHd}}(X\leadsto Y)\leq k$ , which implies $i\leq k+1$ and $j\geq r-k$ . Consequently, there are no substitutions in $X[c_{k+1}\mathinner{.\,.}c_{r-k}]$ . $\hfill\blacktriangleleft$

Lemma 30.

Consider strings $X$ and $Y$ with $X\approx Y$ . Let $a,b\in[1,\lvert Y\rvert]$ such that $a\leq b$ and $Y[a]$ is minimal in $Y[a\mathinner{.\,.}b]$ . Then $X[1\mathinner{.\,.}a]\cdot X(b\mathinner{.\,.}\lvert X\rvert]\approx Y[1% \mathinner{.\,.}a]\cdot Y(b\mathinner{.\,.}\lvert X\rvert]$ .

Proof.

The assumption that $X\approx Y$ , together with Fact 8 and 9, imply that $X[a]$ is minimal in $X[a\mathinner{.\,.}b]$ . For $Z\in\{X,Y\}$ , let $\hat{Z}=Z[1\mathinner{.\,.}a]\cdot Z(b\mathinner{.\,.}\lvert Z\rvert]$ . It is easy to see that the following hold:

$\blacksquare$

For $i\in[1,a]$ , $\textnormal{{psv}}_{\hat{Z}}(i)=\textnormal{{psv}}_{Z}(i)$ . (This is trivial.)
$\blacksquare$

For $i\in(a,\lvert\hat{Z}\rvert]$ with $\textnormal{{psv}}_{Z}(i+b-a)\in(b,\lvert Z\rvert]$ , we have $\textnormal{{psv}}_{\hat{Z}}(i)=\textnormal{{psv}}_{Z}(i+b-a)-b+a$ .
$\blacksquare$

For $i\in(a,\lvert\hat{Z}\rvert]$ with $\textnormal{{psv}}_{Z}(i+b-a)\in(a,b]$ , we have $\textnormal{{psv}}_{\hat{Z}}(i)=a$ .
$\blacksquare$

For $i\in(a,\lvert\hat{Z}\rvert]$ with $\textnormal{{psv}}_{Z}(i+b-a)\in[1,a]$ , we have $\textnormal{{psv}}_{\hat{Z}}(i)=\textnormal{{psv}}_{Z}(i+b-a)$ .

Note that the definition of $\textnormal{{psv}}_{\hat{Z}}$ depends only on the $\textnormal{{psv}}_{Z}$ array. Since $X\approx Y$ , we have that $\textnormal{{psv}}_{X}=\textnormal{{psv}}_{Y}$ by Lemma 9. Therefore, it follows that $\textnormal{{psv}}_{\hat{X}}=\textnormal{{psv}}_{\hat{Y}}$ . By applying Lemma 9 again, we conclude that $\hat{X}\approx\hat{Y}$ . $\hfill\blacktriangleleft$

Lemma 31.

Consider $p,r,k\in\mathbb{Z}_{+}$ and strings $X=X_{1}UX_{2}$ and $Y=Y_{1}VY_{2}$ such that all of the following hold:

$\blacksquare$

$\lvert X_{1}\rvert=\lvert Y_{1}\rvert$ , $\lvert X_{2}\rvert=\lvert Y_{2}\rvert$ , and $\lvert U\rvert=\lvert V\rvert=rp$ , where $r\geq 2k+3$ ;
$\blacksquare$

$U\approx V$ ;
$\blacksquare$

there is no position $i\in[\lvert Y_{1}V\rvert+1\mathinner{.\,.}\lvert Y\rvert]$ such that $\textnormal{{psv}}_{Y}(i)\in[\lvert Y_{1}\rvert+1\mathinner{.\,.}\lvert Y_{1}V% \rvert-p]$ ;
$\blacksquare$

if we define $\forall i\in[1,r]:c_{i}:=\lvert X_{1}\rvert+(i-1)p+1$ , then $X[c_{i}]$ is a minimum in $X[c_{i}\mathinner{.\,.}c_{r}+p)$ , and $Y[c_{i}]$ is a minimum in $Y[c_{i}\mathinner{.\,.}c_{r}+p)$ .

Then $\textnormal{{CHd}}_{k}(\hat{X}\leadsto\hat{Y})=\textnormal{{CHd}}_{k}(X% \leadsto Y)$ , where

\hat{X}=X[1\mathinner{.\,.}c_{k+1}]\cdot X(c_{r-k}-p\mathinner{.\,.}\lvert X% \rvert]\quad\text{and}\quad\hat{Y}=Y[1\mathinner{.\,.}c_{k+1}]\cdot Y(c_{r-k}-% p\mathinner{.\,.}\lvert Y\rvert].

Proof.

It suffices to prove the following two claims, which together imply the statement.

Claim 32.

$\textnormal{{CHd}}(X\leadsto Y)\leq k$ implies $\textnormal{{CHd}}(\hat{X}\leadsto\hat{Y})\leq\textnormal{{CHd}}(X\leadsto Y)$ .

Claim 33.

$\textnormal{{CHd}}(\hat{X}\leadsto\hat{Y})\leq k$ implies $\textnormal{{CHd}}(\hat{X}\leadsto\hat{Y})\geq\textnormal{{CHd}}(X\leadsto Y)$ .

Proof of Claim 32.

Assume that $\textnormal{{CHd}}(X\leadsto Y)\leq k$ and consider any sequence of $\textnormal{{CHd}}(X\leadsto Y)$ substitutions that transform $X$ into a string $X^{\prime}$ with $X^{\prime}\approx Y$ . By Lemma 29, we have $X^{\prime}=X^{\prime}[1\mathinner{.\,.}c_{k+1})\cdot X[c_{k+1}\mathinner{.\,.}% c_{r-k}]\cdot X^{\prime}(c_{r-k}\mathinner{.\,.}\lvert X\rvert]$ . Note that we can perform the same sequence of substitutions (with an appropriate shift) on $\hat{X}$ as well. Hence, there is a sequence of $\textnormal{{CHd}}(X\leadsto Y)$ substitutions that transforms $\hat{X}$ into

\hat{X}^{\prime}:=X^{\prime}[1\mathinner{.\,.}c_{k+1})\cdot X[c_{k+1}]\cdot X(% c_{r-k}-p\mathinner{.\,.}c_{r-k}]\cdot X^{\prime}(c_{r-k}\mathinner{.\,.}% \lvert X\rvert].

It remains to be shown that $\hat{X}^{\prime}\approx\hat{Y}$ , which implies $\textnormal{{CHd}}(\hat{X}\leadsto\hat{Y})\leq\textnormal{{CHd}}(X\leadsto Y)$ . Note that $\hat{X}^{\prime}$ and $\hat{Y}$ can be obtained by deleting fragments $X^{\prime}(c_{k+1}\mathinner{.\,.}c_{r-k}-p]$ and $Y(c_{k+1}\mathinner{.\,.}c_{r-k}-p]$ from $X^{\prime}$ and $Y$ , respectively. By the definition of $Y$ , we know that $Y[c_{k+1}]$ is a minimum in $Y[c_{k+1}\mathinner{.\,.}c_{r-k}-p]$ . Hence, we can apply Lemma 30 to $X^{\prime}$ and $Y$ with $a=c_{k+1}$ and $b=c_{r-k}-p$ , thus obtaining $\hat{X}^{\prime}\approx\hat{Y}$ . $\hfill\vartriangleleft$

Proof of Claim 33.

Assume that $\textnormal{{CHd}}(\hat{X}\leadsto\hat{Y})\leq k$ and consider any sequence of $\textnormal{{CHd}}(\hat{X}\leadsto\hat{Y})$ substitutions that transform $\hat{X}$ into a string $\hat{X}^{\prime}$ with $\hat{X}^{\prime}\approx\hat{Y}$ . It can be readily verified that the strings $\hat{X}$ and $\hat{Y}$ still satisfy the conditions of Lemma 29 with parameter $\hat{r}=2k+2$ . Therefore, we have:

	$\displaystyle\hat{X}^{\prime}={}$	$\displaystyle\hat{X}^{\prime}[1\mathinner{.\,.}c_{k+1})\cdot\hat{X}[c_{k+1}% \mathinner{.\,.}c_{\hat{r}-k}]\cdot\hat{X}^{\prime}(c_{\hat{r}-k}\mathinner{.% \,.}\lvert\hat{X}\rvert]$
	$\displaystyle{}={}$	$\displaystyle\hat{X}^{\prime}[1\mathinner{.\,.}c_{k+1})\cdot X[c_{k+1}]\cdot X% (c_{r-k}-p\mathinner{.\,.}c_{r-k}]\cdot\hat{X}^{\prime}(c_{k+2}\mathinner{.\,.% }\lvert\hat{X}\rvert].$

We observe that the same sequence of substitutions can also be applied directly to $X$ , resulting in the string: $X^{\prime}=\hat{X}^{\prime}[1\mathinner{.\,.}c_{k+1})\cdot X[c_{k+1}\mathinner% {.\,.}c_{r-k}]\cdot\hat{X}^{\prime}(c_{k+2}\mathinner{.\,.}\lvert\hat{X}\rvert]$ .

It remains to be shown that $X^{\prime}\approx Y$ , which implies $\textnormal{{CHd}}(\hat{X}\leadsto\hat{Y})\geq{\textnormal{{CHd}}(X\leadsto Y)}$ . Note that $\hat{X}^{\prime}$ and $X^{\prime}$ , as well as $\hat{Y}$ and $Y$ , share a prefix of length $c_{k+1}$ . Due to ${\hat{X}^{\prime}\approx\hat{Y}}$ , combined with Fact 8 and 9, it is clear that, for every $x\in[1\mathinner{.\,.}c_{k+1}]$ , $\textnormal{{psv}}_{X^{\prime}}(x)=\textnormal{{psv}}_{\hat{X}^{\prime}}(x)=% \textnormal{{psv}}_{\hat{Y}}(x)=\textnormal{{psv}}_{Y}(x)$ .

Next, we observe that $X^{\prime}[c_{k+1}\mathinner{.\,.}c_{r-k}]=X[c_{k+1}\mathinner{.\,.}c_{r-k}]$ . Recall that $X[c_{k+1}]$ and $Y[c_{k+1}]$ are minimal in $X[c_{k+1}\mathinner{.\,.}c_{r-k}]$ and $Y[c_{k+1}\mathinner{.\,.}c_{r-k}]$ , respectively. Due to $U\approx V$ , combined with Fact 8 and 9, we have $\forall x\in(c_{k+1},c_{r-k}]:\textnormal{{psv}}_{X^{\prime}}(x)=\textnormal{{% psv}}_{Y}(x)\geq c_{k+1}$ .

Finally, we consider $x\in(c_{r-k},\lvert X\rvert]$ . Let $\hat{x}=x-\lvert X\rvert+\lvert\hat{X}\rvert$ . We observe that $\hat{X}^{\prime}$ and $X^{\prime}$ , as well as $\hat{Y}$ and $Y$ , share a suffix of length $\ell:=\lvert X\rvert-c_{r-k}+p$ . If $\textnormal{{psv}}_{Y}(x)>c_{r-k}-p$ , then $\hat{X}^{\prime}\approx\hat{Y}$ already implies $\textnormal{{psv}}_{\hat{X}^{\prime}}(\hat{x})=\textnormal{{psv}}_{\hat{Y}}(% \hat{x})$ . It remains to consider the case when $x\in(c_{r-k},\lvert X\rvert]$ and $\textnormal{{psv}}_{Y}(x)\leq c_{r-k}-p$ . In this case, since $Y[c_{r-k}]$ is minimal in $Y[c_{r-k}\mathinner{.\,.}c_{r}+p)$ , it holds that $x\geq c_{r}+p=\lvert Y_{1}V\rvert+1$ , and, by the condition of the lemma, $\textnormal{{psv}}_{Y}(x)\leq\lvert Y_{1}\rvert=c_{1}-1$ . Note that $\textnormal{{psv}}_{\hat{Y}}(\hat{x})=\textnormal{{psv}}_{Y}(x)$ , as we obtained $\hat{Y}$ by merely deleting some elements between $\textnormal{{psv}}_{Y}(x)$ and $x$ . Due to $\hat{X}^{\prime}\approx\hat{Y}$ , we have $\textnormal{{psv}}_{\hat{X}^{\prime}}(\hat{x})=\textnormal{{psv}}_{\hat{Y}}(% \hat{x})$ . Finally, we obtain $X^{\prime}$ from $\hat{X}^{\prime}$ by inserting into $\hat{X}^{\prime}$ values that are at least as large as $\hat{X}^{\prime}[c_{k+1}]=X[c_{k+1}]$ between positions $\textnormal{{psv}}_{\hat{X}^{\prime}}(\hat{x})$ and $\hat{x}$ . Since $\hat{X}^{\prime}[c_{k+1}]\in(\textnormal{{psv}}_{\hat{X}^{\prime}}(\hat{x}),% \hat{x})$ , we know that $\hat{X}^{\prime}[\hat{x}]<\hat{X}^{\prime}[c_{k+1}]$ , and thus all inserted values are at least $\hat{X}^{\prime}[\hat{x}]$ . Thus, $\textnormal{{psv}}_{X^{\prime}}(x)=\textnormal{{psv}}_{\hat{X}^{\prime}}(\hat{% x})=\textnormal{{psv}}_{\hat{Y}}(\hat{x})=\textnormal{{psv}}_{Y}(x)$ , as required. $\hfill\vartriangleleft$

The combination of the two claims yields that either both $\textnormal{{CHd}}(\hat{X}\leadsto\hat{Y})$ and $\textnormal{{CHd}}(X\leadsto Y)$ are at most $k$ and are in fact equal, or they are both greater than $k$ . $\hfill\blacktriangleleft$

A symmetric claim holds for next-smaller-values. For completeness, we provide a proof of the corresponding lemma below in the full version.

Lemma 34 (analogue of Lemma 31).

Consider $p,r,k\in\mathbb{Z}_{+}$ and strings $X=X_{1}UX_{2}$ and $Y=Y_{1}VY_{2}$ such that all of the following hold:

$\blacksquare$

$\lvert X_{1}\rvert=\lvert Y_{1}\rvert$ , $\lvert X_{2}\rvert=\lvert Y_{2}\rvert$ , and $\lvert U\rvert=\lvert V\rvert=rp$ , where $r\geq 2k+3$ ;
$\blacksquare$

$U\approx V$ ;
$\blacksquare$

there is no position $i\in[1,\lvert Y_{1}\rvert]$ such that $\textnormal{{nsv}}_{Y}(i)\in[\lvert Y_{1}\rvert+p+1\mathinner{.\,.}\lvert Y_{1% }V\rvert]$ ;
$\blacksquare$

if we define $\forall i\in[1,r]:c_{i}:=\lvert X_{1}\rvert+ip$ , then $X[c_{i}]$ is a minimum in $X(c_{1}-p\mathinner{.\,.}c_{i}]$ , and $Y[c_{i}]$ is a minimum in $Y(c_{1}-p\mathinner{.\,.}c_{i}]$ .

Then $\textnormal{{CHd}}_{k}(\hat{X}\leadsto\hat{Y})=\textnormal{{CHd}}_{k}(X% \leadsto Y)$ , where

\hat{X}=X[1\mathinner{.\,.}c_{k+1}+p)\cdot X[c_{r-k}\mathinner{.\,.}\lvert X% \rvert]\quad\text{and}\quad\hat{Y}=Y[1\mathinner{.\,.}c_{k+1}+p)\cdot Y[c_{r-k% }\mathinner{.\,.}\lvert Y\rvert].

We are now ready to prove the main algorithmic result of this section.

Lemma 35.

Let $n,m,k,p,\Delta\in\mathbb{Z}_{+}$ satisfy $n\leq 3m/2$ , $p<\Delta$ , $k<\Delta$ , and $k\Delta\leq\sqrt{m}/128$ . Given $k$ , $p$ , $\Delta$ , a text $T[1\mathinner{.\,.}n]$ , a pattern $P[1\mathinner{.\,.}m]$ , and a fragment $P[\ell\mathinner{.\,.}r)$ of length at least $m/{(4\Delta)}$ with minimum CT-block-period $p$ , we can compute ${\textnormal{{CHd}}_{k}(T[i\mathinner{.\,.}i+m)\leadsto P)}$ for all $i\in[1,n-m+1]$ in $\mathcal{O}(mk^{4}\Delta)$ time.

Proof.

Due to $\Delta^{2}\leq m/(128^{2}k^{2})$ , the fragment $P[\ell\mathinner{.\,.}r)$ is of length at least $m/{(4\Delta)}\geq{p\cdot m/(4\Delta^{2})}>p\cdot 1000k^{2}$ and hence consists of at least $1000k^{2}$ blocks of length $p$ ; namely, $P[\ell+ip\mathinner{.\,.}\ell+(i+1)p)$ for $i\in[0,(r-\ell)/p)$ . In any $k$ -approximate CT-occurrence of $P[\ell\mathinner{.\,.}r)$ in $T$ , at least $1000k^{2}-k\geq 999k^{2}$ of those blocks are aligned with fragments of $T$ that CT-match them. These blocks are partitioned into at most $k+1$ sets of contiguous blocks by the at most $k$ blocks that are aligned with fragments of $T$ that do not CT-match them. Hence, in any $k$ -approximate CT-occurrence of $P[\ell\mathinner{.\,.}r)$ in $T$ , there exists a fragment $F$ of $P[\ell\mathinner{.\,.}r)$ that consists of at least $999k^{2}/(k+1)>100k$ blocks and is CT-matched exactly.²²2Note that it might be a different fragment for each $k$ -approximate CT-occurrence of $P[\ell\mathinner{.\,.}r)$ in $T$ . We have $\lvert F\rvert=\Omega(\lvert P[\ell\mathinner{.\,.}r)]\rvert/k)\supseteq\Omega% (m/(k\Delta))$ . Further, the CT-block-periodicity of $P[\ell\mathinner{.\,.}r)$ implies that $F\approx P[\ell\mathinner{.\,.}\ell+\lvert F\rvert)$ and, combined with Lemma 19, that $F$ has minimum CT-block-period $p$ .

For a string $X$ , a block $X[i\mathinner{.\,.}i+p)$ of length $p$ with $i-p,i+2p-1\in[1,\lvert X\rvert]$ , is bad if $X[i-p\mathinner{.\,.}i+2p)\not\approx P[\ell\mathinner{.\,.}\ell+3p)$ and good otherwise. Intuitively, if we have many bad blocks in $P$ , at least one of them has to be aligned with a bad block in the text. In this case, we exploit this property to obtain a few candidate starting positions of $k$ -approximate CT-matches. We then verify each of them using Lemma 24. In the complementary case, the pattern is almost periodic (that is, it almost entirely consists of good blocks). We exploit this by trimming long pairs of fragments (one in $T$ and one in $P$ ) that are composed solely of good blocks using either Lemma 31 or Lemma 34 before invoking Lemma 24.

We compute a fragment $\Phi=P[\ell^{\prime}\mathinner{.\,.}r^{\prime})$ of $P$ by extending $P[\ell\mathinner{.\,.}r)$ blockwise to the left (and to the right) by prepending (resp. appending) blocks of $p$ characters until we either accumulate $3k+1$ bad blocks in that direction or there are fewer than $2p$ characters left in that direction – in the latter case, we almost reach the beginning (resp. end) of $P$ .

Figure 4: Illustrations for Lemma 35. Gray (hatched) blocks are explicitly (resp., implicitly) bad.

Case I: Enough blocks accumulated in at least one direction.

Assume, without loss of generality, that we accumulated $3k+1$ bad blocks while extending $P[\ell\mathinner{.\,.}r)$ to the left.

We employ the linear-time exact CT-matching algorithm of Lemma 6 to compute all exact CT-occurrences of $F:=P[\ell\mathinner{.\,.}\ell+100kp)$ in $T$ . By Lemma 22, these CT-occurrences can be partitioned into $\mathcal{O}(n/\lvert F\rvert)\subseteq\mathcal{O}(k\Delta)$ arithmetic progressions with common difference $p$ such that the CT-occurrences in each of the progressions span a CT-run of length $\Omega(m/(k\Delta))$ with minimum CT-block-period $p$ . Let $\mathcal{R}$ denote the set of CT-runs in $T$ that are spanned by the exact CT-occurrences of $F$ .

Let us fix a CT-run $T[a\mathinner{.\,.}b]=R\in\mathcal{R}$ . We extend $R$ to the left using a procedure identical to the one performed on $P[\ell\mathinner{.\,.}r)$ until we either accumulate $3k+1$ bad blocks or the fragment contains $T[2p]$ . Consider aligning the pattern with a fragment $T[i\mathinner{.\,.}i+m)$ such that a fragment of $P[\ell\mathinner{.\,.}r)$ that CT-matches $F$ is aligned with a fragment of $R$ that CT-matches it. By Lemma 22, any such alignment satisfies $a-i+1\equiv\ell\pmod{p}$ , that is, it perfectly aligns the block boundaries of $P[\ell\mathinner{.\,.}r)$ and $R$ . In such an alignment, if a bad (resp. good) block of the pattern is aligned with a good (resp. bad) block of the text, at least one substitution is required in either that text block or one of its two neighbours in any sequence of substitutions that transforms $T[i\mathinner{.\,.}i+m)$ into a string $X\approx P$ . Thus, $k$ substitutions performed on $T[i\mathinner{.\,.}i+m)$ can fix at most $3k$ misaligned pairs (that is, pairs consisting of a bad block in one of the strings and a good block in the other). Therefore, at least one of the leftmost $9k+1$ bad blocks of $\Phi$ must be aligned with one of the at most $3k+1$ bad blocks in the extension of $R$ . There are only $\mathcal{O}(k^{2})$ ways to align such a pair of bad blocks, each yielding a candidate starting position of a $k$ -approximate CT-occurrence of $P$ in $T$ . The described procedure can be implemented naively in $\mathcal{O}(m)$ time.

We perform this procedure for all CT-runs in $\mathcal{R}$ , thus obtaining $\mathcal{O}(\lvert\mathcal{R}\rvert\cdot k^{2})=\mathcal{O}(k^{3}\Delta)$ candidate starting positions. We then invoke Lemma 24 for each such position. In total, this takes time $\mathcal{O}(k^{3}\Delta\cdot mk)=\mathcal{O}(mk^{4}\Delta)$ .

Case II: The pattern is almost CT-block-periodic.

In the complementary case, we did not accumulate $9k+1$ bad blocks in either direction. Thus, $P=X_{P}B_{P}Y_{P}$ where $\lvert X_{P}\rvert,\lvert Y_{P}\rvert<2p$ and $B_{P}$ consists of $p$ -length blocks, at most $6k$ of which are bad.

Claim 36.

In $\mathcal{O}(n)$ time, we can either decide that $P$ has no $k$ -approximate CT occurrences in $T$ or compute a fragment $T^{\prime}=T[t_{1}\mathinner{.\,.}t_{2})=X_{T}B_{T}Y_{T}$ such that the following hold:

$\blacksquare$

for all $i\in[1,n-m+1]$ , $\textnormal{{CHd}}_{k}(T[i\mathinner{.\,.}i+m)\leadsto P)\leq k$ , implies that $i,i+m\in[t_{1},t_{2}]$ and $i\equiv t_{1}\pmod{p}$ .
$\blacksquare$

$\lvert X_{T}\rvert=\lvert X_{P}\rvert$ and $\lvert Y_{T}\rvert=\lvert Y_{P}\rvert$ ,

Moreover, $B_{T}$ is partitioned into $p$ -length blocks $\mathcal{O}(k)$ of which are explicitly marked as bad.

Proof.

By Lemma 19, the fragment $\Pi:=P[\ell\mathinner{.\,.}\ell+3p)$ has minimum CT-block-period $p$ . Thus, by Lemma 22, any two exact CT-occurrences of $\Pi$ in $T$ are at distance at least $p$ and there are at most $n/p$ CT-occurrences in total.

Now, any $k$ -approximate CT-occurrence of $P$ in $T$ implies a large number of exact CT-occurrences of $\Pi$ at positions that are in a single equivalence class modulo $p$ , with each such CT-occurrence corresponding to aligning a good block of $B_{P}$ with a fragment of $T$ . Specifically, by accounting for the at most $k$ substitutions (each potentially affecting three good blocks), the at most $6k$ bad blocks in $P$ , as well as $X_{P}$ and $X_{T}$ which are of total length at most $4p$ , we conclude that we must have at least ${\lfloor(m-4p)/p\rfloor}-6k-3k\geq m/p-13k$ such exact CT-occurrences. The inequalities $k\Delta\leq\sqrt{m}/128$ and $p<\Delta$ imply that $13kp<\sqrt{m}/4$ , and hence $m/p-13k\geq(m-\sqrt{m}/4)/p$ . Since we have a total of $n/p$ CT-occurrences of $\Pi$ in $T$ and $n/p\leq 3m/(2p)<2(m-\sqrt{m}/4)/p$ , there is at most one residue modulo $p$ , say $\rho$ , with at least $m/p-\sqrt{m}/p$ CT-occurrences of $\Pi$ starting at a positions equivalent to $\rho$ modulo $p$ .

We compute all exact CT-occurrences of $\Pi$ in $T$ in $\mathcal{O}(n)$ time using Lemma 6 and identify the majority residue modulo $p$ , say $\rho$ , resolving ties arbitrarily. If the CT-occurrences of $\Pi$ at positions of $T$ equivalent to $\rho$ modulo $p$ are fewer than $m/p-\sqrt{m}/p$ , we conclude that $P$ does not have any $k$ -approximate CT-occurrences in $T$ and terminate the algorithm. We henceforth, assume that we are in the complementary case.

We select $y$ as the leftmost position in $T$ such that $y\geq n/2$ and $y\equiv\rho\pmod{p}$ . We extend the fragment $T[y\mathinner{.\,.}y+p)$ in each direction until we either accumulate $9k+1$ bad blocks or there are fewer than $2p$ characters left. Let $T[a\mathinner{.\,.}b)$ denote the obtained fragment.

Any $k$ -approximate CT-occurrence $T[i\mathinner{.\,.}i+m)$ of $P$ in $T$ must align $B_{P}$ with a fragment of the form $T[a+ip\mathinner{.\,.}b-jp)$ for nonnegative integers $i$ and $j$ . Further, in this CT-occurrence, $B_{P}$ must be aligned with a fragment of $T$ that contains $T[\lfloor n/2\rfloor]$ . Now, observe that at most $9k$ bad blocks of $T$ can be contained in $T[i\mathinner{.\,.}i+m)$ , as at most $6k$ of them can be aligned with CT-matching bad blocks of $P$ and the at most $k$ substitutions may fix at most $3k$ pairs of bad blocks in $T$ with good blocks in $P$ . This implies that $i+\lvert X_{P}\rvert,i+\lvert X_{P}B_{P}\rvert\in[a,b]$ .

Next, we define the boundaries $t_{1}$ and $t_{2}$ , and describe the decomposition $T^{\prime}=X_{T}B_{T}Y_{T}$ . Let $t_{1}$ be the smallest positive integer in $\{a+ip-\lvert X_{P}\rvert:i\in\{0,1,2\}\}$ , let $t_{2}$ be the largest integer in $\{b-ip+\lvert Y_{P}\rvert:i\in\{0,1,2\}\}\cap[1,n]$ , and set $T^{\prime}=T[t_{1}\mathinner{.\,.}t_{2})$ . Since, for any approximate CT-occurrence $T[i\mathinner{.\,.}i+m)$ we have $i+\lvert X_{P}\rvert,i+\lvert X_{P}B_{P}\rvert\in[a,b]$ , this ensures that $i,i+m\in[t_{1},t_{2}]$ . Further we have that $i\equiv t_{1}\pmod{p}$ since $i+\lvert X_{P}\rvert\equiv a\pmod{p}$ . The partition of $T^{\prime}$ is then defined as: $X_{T}=T[t_{1}\mathinner{.\,.}t_{1}+\lvert X_{P}\rvert)$ , $B_{T}=T[t_{1}+\lvert X_{P}\rvert\mathinner{.\,.}t_{2}-\lvert Y_{P}\rvert)$ , $Y_{T}=T[t_{2}-\lvert Y_{P}\rvert\mathinner{.\,.}t_{2})$ . Finally, we return $t_{1}$ , $t_{2}$ , and the bad blocks in $B_{T}$ . $\hfill\vartriangleleft$

We also designate each block in $B_{P}$ as implicitly bad if it contains a position $i$ such that there exists a position $j$ in either an explicitly bad block or in $J:=[1,\lvert X_{P}\rvert]\cup(\lvert X_{P}B_{P}\rvert,\lvert P\rvert]$ , such that $i=\textnormal{{psv}}_{P}(j)$ or $i=\textnormal{{nsv}}_{P}(j)$ . Note that the number of implicitly bad blocks is $\mathcal{O}(kp)\subseteq\mathcal{O}(k\Delta)$ (since $p<\Delta$ ) as each (explicitly) bad block implies $\mathcal{O}(p)$ implicitly bad ones and $J$ implies $\mathcal{O}(p)$ implicitly bad blocks. This designation is necessary because substitutions are local operations, whereas CT-equivalence is a global property. Although substitutions directly modify values within explicitly bad blocks, a single substitution can indirectly affect many distant positions. In particular, if a substitution occurs at position $i$ such that $i=\textnormal{{psv}}_{P}(j)$ or $i=\textnormal{{nsv}}_{P}(j)$ for some position $j$ , then the values $\textnormal{{psv}}_{P}(j)$ or $\textnormal{{psv}}_{P}(j)$ may change. To ensure that Lemma 31 can be invoked to trim long sequences of good blocks, we must account for all blocks that could potentially interact with either the boundary fragments or the blocks aligned with blocks that contain substitutions.

By Claim 36, it suffices to compute $\textnormal{{CHd}}_{k}(T[i\mathinner{.\,.}i+m)\leadsto P)$ for each of the $\mathcal{O}(m/p)$ positions in $T$ that satisfy $i\equiv t_{1}\pmod{p}$ and $i,i+m\in[t_{1},t_{2}]$ . Let $G=T[i\mathinner{.\,.}i+m)$ . $G$ inherits its block-decomposition from $B_{T}$ , as well as the classification of some blocks as bad. We call the considered position $i$ an overlap position if there exist positions $\pi$ in $P$ and $\phi$ in $G$ that belong to (implicitly or explicitly) bad blocks and satisfy $\lvert\pi-\phi\rvert\leq 6kp$ , and a non-overlap position otherwise. We treat overlap and non-overlap positions differently:

$\blacksquare$

If $i$ is an overlap position, we employ Lemma 24 to compute $\textnormal{{CHd}}_{k}(G\leadsto P)$ in $\mathcal{O}(mk)$ time. The number of overlap positions is $\mathcal{O}(k^{3}p)=\mathcal{O}(k^{3}\Delta)$ since we require one of the $\mathcal{O}(kp)$ (implicitly or explicitly) bad blocks in $B_{P}$ to be within $\mathcal{O}(k)$ blocks of one of the $\mathcal{O}(k)$ bad blocks in $B_{T}$ . The total time required for overlap positions is thus $\mathcal{O}(mk^{4}\Delta)$ . Note that we can efficiently enumerate all the overlap positions using the list of bad blocks for both $B_{P}$ and $B_{T}$ .
$\blacksquare$

If $i$ is a non-overlap position, then we can show that $\textnormal{{CHd}}_{k}(G\leadsto P)$ only depends on the parts of the alignment of $G$ and $P$ in the $\mathcal{O}(k)$ -block vicinity of the (implicitly or explicitly) bad blocks. More precisely, Lemmas 31 and 34 will allow us to delete most of the good blocks, significantly reducing the lengths of $G$ and $P$ prior to performing the comparison of Lemma 24. We first describe this trimming procedure, and then justify that the conditions for Lemmas 31 and 34 are indeed satisfied.

We use Lemma 31 if $P[\ell^{\prime}]$ is the leftmost minimum of $\Phi$ and Lemma 34 otherwise, that is, if the leftmost minimum is $P[r^{\prime}-1]$ . Conceptually, we perform the following procedure. We traverse the lists of bad blocks in each of $G$ and $P$ from left to right in parallel in $\mathcal{O}(k)$ time. Whenever we encounter a maximal pair of fragments $U=G[x_{1}\mathinner{.\,.}x_{2})$ and $V=P[x_{1}\mathinner{.\,.}x_{2})$ of length at least $(6k+1)p$ that only consist of blocks that are not (implicitly or explicitly) bad, we replace $G[x_{1}\mathinner{.\,.}x_{2})$ with $U[1\mathinner{.\,.}3kp]\cdot U(\lvert U\rvert-3kp\mathinner{.\,.}\lvert U\rvert]$ and $P[x_{1}\mathinner{.\,.}x_{2})$ with $V[1\mathinner{.\,.}3kp]\cdot V(\lvert V\rvert-3kp\mathinner{.\,.}\lvert V\rvert]$ . A repeated application of either Lemma 31 or Lemma 34 guarantees that $\textnormal{{CHd}}_{k}(G\leadsto P)=\textnormal{{CHd}}_{k}(G^{\prime}\leadsto P% ^{\prime})$ , where $G^{\prime}$ and $P^{\prime}$ are the strings obtained from $G$ and $P$ , respectively. Instead of making the replacements on $G$ and $P$ , we explicitly construct $G^{\prime}$ and $P^{\prime}$ by copying the fragments of $G$ and $P$ that are not deleted by the conceptual procedure described above.

As we have $\mathcal{O}(kp)$ (implicitly or explicitly) bad blocks in $P$ and $\mathcal{O}(k)$ bad blocks in $G$ , and since each bad block prevents $\mathcal{O}(k)$ blocks from being trimmed, we have $\lvert G^{\prime}\rvert=\lvert P^{\prime}\rvert=\mathcal{O}(k^{2}p^{2})$ . The computation of $\textnormal{{CHd}}_{k}(G\leadsto P)$ using Lemma 24 thus takes $\mathcal{O}(k^{2}p^{2}\cdot k)$ time and returns $\textnormal{{CHd}}_{k}(G\leadsto P)$ . Over all $\mathcal{O}(m/p)$ non-overlap positions, the total time required is $\mathcal{O}(m/p\cdot k^{2}p^{2}\cdot k)=\mathcal{O}(mpk^{3})=\mathcal{O}(mk^{3% }\Delta)$ .
It remains to be shown that the described applications of Lemma 31 are valid if $P[\ell^{\prime}]$ is the leftmost minimum of $\Phi$ ; applications of Lemma 34 are valid in the remaining case by symmetric arguments. First, note that $p$ is a CT-block-period of $U$ and $V$ by Lemma 22, and they both have their leftmost minimum at their first positions.
- –
  
  The first condition of Lemma 31 holds trivially by our assumptions with $r=(x_{2}-x_{1})/p$ .
- –
  
  The second condition of Lemma 31 holds by Corollary 18 as $p$ is a CT-block-period of both $U$ and $V$ , and $U[1\mathinner{.\,.}2p]\approx P[\ell+p\mathinner{.\,.}\ell+3p)\approx V[1% \mathinner{.\,.}2p]$ .
- –
  
  The third condition of Lemma 31 holds due to the facts that (a) by the definition of implicitly bad blocks, there is no position $j$ outside a good block with $\textnormal{{psv}}_{P}(j)\in[x_{1}\mathinner{.\,.}x_{2}-p)$ , and (b) for each position $j$ in a good block, $\textnormal{{psv}}_{P}(j)$ is at least $j-p$ by an application of Lemma 15 to $\Phi$ .
- –
  
  The fourth condition of Lemma 31 follows by applying Lemma 15 to $U$ and $V$ .

$\hfill\blacktriangleleft$

4.4 Wrap-Up

Theorem 1. [Restated, see original statement.]

The Approximate CT-Matching with Substitutions problem can be solved in $\mathcal{O}(n\sqrt{m}\cdot k^{2.5})$ time for $k\in[1,\lfloor m^{1/5}\rfloor]$ and in $\mathcal{O}(nk^{5})$ time for any $k\in[\lfloor m^{1/5}\rfloor,m]$ .

Proof.

We can assume that $k<m^{1/4}/128$ ; otherwise, the algorithm of Kim and Han [21], which simply invokes Lemma 24 for $k$ , $P$ , and $T[i\mathinner{.\,.}i+m)$ for each $i\in[1,n-m+1]$ , runs in $\mathcal{O}(nmk)\subseteq\mathcal{O}(nk^{5})$ time.

For $\Delta\in\mathbb{Z}_{+}$ (to be specified later) satisfying $k\Delta\leq\sqrt{m}/128$ , we apply Lemma 26 to $P$ . We either obtain a CT-rainbow of $\Delta$ disjoint fragments in $P$ , or a fragment of length at least $m/{(4\Delta)}$ with its minimum CT-block-period $p<\Delta$ . This takes $\mathcal{O}(m\Delta)$ time.

We then apply the so-called standard trick to reduce the given instance of Approximate CT-Matching with Substitutions to $\mathcal{O}(n/m)$ instances of the same problem with the same pattern $P$ , the same threshold $k$ , and the text being a fragment of $T$ of length at most $3m/2$ . For $i\in[0,\lfloor 2n/m\rfloor]$ , define $T_{i}:=T[1+\lfloor i\cdot m/2\rfloor\mathinner{.\,.}\min\{\lfloor(i+3)\cdot m/% 2\rfloor,n+1\})$ . It is readily verified that each $m$ -length fragment of $T$ appears in precisely one of the $T_{i}$ s.

We then apply either Lemma 28 or Lemma 35 (depending on the outcome of the analysis of the pattern according to Lemma 26) to solve an instance of Approximate CT-Matching with Substitutions separately for each $T_{i}$ . In the end, we merge the results.

Each instance is solved in $\mathcal{O}(mk^{4}\Delta+m^{2}k/\Delta)$ time. The total complexity over all $\mathcal{O}(n/m)$ instances is therefore $\mathcal{O}((n/m)(mk^{4}\Delta+m^{2}k/\Delta))=\mathcal{O}(nk^{4}\Delta+nmk/\Delta)$ . We now distinguish between two cases:

$\blacksquare$

If $k\leq\lfloor m^{1/5}/128^{2/5}\rfloor$ , we balance the two terms in the complexity by setting $\Delta=\lfloor\sqrt{m}/(128\cdot k^{1.5})\rfloor$ . Since $k\Delta\leq\sqrt{m}/128$ , and $2k\leq\Delta$ , the time complexity is

$\mathcal{O}\left(nk^{4}\cdot\frac{\sqrt{m}}{k^{1.5}}+\frac{nmk}{\sqrt{m}/k^{1.% 5}}\right)=\mathcal{O}(n\sqrt{m}\cdot k^{2.5}).$
$\blacksquare$

Else, we have $k\in(\lfloor m^{1/5}/128^{2/5}\rfloor,\lfloor m^{1/4}/128\rfloor)$ . We set $\Delta=2k$ , noting that $k\Delta=2k^{2}$ . Since $k<m^{1/4}/128$ , we have $k^{2}<\sqrt{m}/128^{2}$ and hence $k\Delta=2k^{2}<\sqrt{m}/128$ . Hence, in this case, the time complexity is

$\mathcal{O}\left(nk^{4}(2k)+\frac{nmk}{2k}\right)=\mathcal{O}(nk^{5}+nm)=% \mathcal{O}(nk^{5}).$

Since $nk^{5}=\Theta(n\sqrt{m}\cdot k^{2.5})$ for all $k\in[\lfloor m^{1/5}/128^{2/5}\rfloor\lfloor m^{1/5}\rfloor]$ , the statement holds. $\hfill\blacktriangleleft$

5 Conclusions and Open Problems

We have presented an efficient algorithm for Approximate CT-Matching with Substitutions. Our algorithm can be seen as a reduction to several instances of computing $\textnormal{{CHd}}(X\leadsto Y)$ for pairs of strings $X$ and $Y$ . We note that any improvement upon the dynamic-programming approach of Kim and Han [21] for this comparison problem would directly yield an improvement over our main result. Interestingly, no (conditional) lower bound is known for either the problem of computing $\textnormal{{CHd}}(X\leadsto Y)$ or Approximate CT-Matching with Substitutions, and devising such a lower bound is another direction for future work. Finally, we hope that our techniques will serve as a foundation for advancing the state of the art in approximate CT-matching under the edit distance.

References

[1] Bastien Auvray, Julien David, Samah Ghazawi, Richard Groult, Gad M. Landau, and Thierry Lecroq. Approximate Cartesian tree matching with one difference. CoRR, abs/2505.09236, 2025. doi:10.48550/arXiv.2505.09236.
[2] Michael A. Bender, Martin Farach-Colton, Giridhar Pemmasani, Steven Skiena, and Pavel Sumazin. Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms, 57(2):75–94, 2005. doi:10.1016/J.JALGOR.2005.08.001.
[3] Dany Breslauer and Zvi Galil. Finding all periods and initial palindromes of a string in parallel. Algorithmica, 14(4):355–366, 1995. doi:10.1007/BF01294132.
[4] Karl Bringmann, Marvin Künnemann, and Philip Wellnitz. Few matches or almost periodicity: Faster pattern matching with mismatches in compressed texts. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 1126–1145. SIAM, 2019. doi:10.1137/1.9781611975482.69.
[5] Domenico Cantone, Simone Faro, and M. Oguzhan Külekci. The order-preserving pattern matching problem in practice. Discret. Appl. Math., 274:11–25, 2020. doi:10.1016/J.DAM.2018.10.023.
[6] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz. Faster approximate pattern matching: A unified approach. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 978–989. IEEE, 2020. doi:10.1109/FOCS46700.2020.00095.
[7] Tamanna Chhabra, Simone Faro, M. Oguzhan Külekci, and Jorma Tarhio. Engineering order-preserving pattern matching with SIMD parallelism. Softw. Pract. Exp., 47(5):731–739, 2017. doi:10.1002/SPE.2433.
[8] Sukhyeun Cho, Joong Chae Na, Kunsoo Park, and Jeong Seop Sim. A fast algorithm for order-preserving pattern matching. Inf. Process. Lett., 115(2):397–402, 2015. doi:10.1016/J.IPL.2014.10.018.
[9] Gianni Decaroli, Travis Gagie, and Giovanni Manzini. A compact index for order-preserving pattern matching. Softw. Pract. Exp., 49(6):1041–1051, 2019. doi:10.1002/SPE.2694.
[10] Erik D. Demaine, Gad M. Landau, and Oren Weimann. On Cartesian trees and range minimum queries. Algorithmica, 68(3):610–625, 2014. doi:10.1007/S00453-012-9683-X.
[11] Nathan J. Fine and Herbert S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 16(1):109–114, 1965. doi:10.2307/2034009.
[12] Johannes Fischer and Volker Heun. Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput., 40(2):465–492, 2011. doi:10.1137/090779759.
[13] Arnab Ganguly, Wing-Kai Hon, Kunihiko Sadakane, Rahul Shah, Sharma V. Thankachan, and Yilin Yang. Space-efficient dictionaries for parameterized and order-preserving pattern matching. In 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016, pages 2:1–2:12, 2016. doi:10.4230/LIPIcs.CPM.2016.2.
[14] Pawel Gawrychowski, Samah Ghazawi, and Gad M. Landau. On indeterminate strings matching. In 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, pages 14:1–14:14, 2020. doi:10.4230/LIPIcs.CPM.2020.14.
[15] Pawel Gawrychowski and Przemyslaw Uznanski. Order-preserving pattern matching with k mismatches. Theor. Comput. Sci., 638:136–144, 2016. doi:10.1016/J.TCS.2015.08.022.
[16] Diptarama Hendrian. Generalized dictionary matching under substring consistent equivalence relations. In WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, pages 120–132, 2020. doi:10.1007/978-3-030-39881-1_11.
[17] Davaajav Jargalsaikhan, Diptarama Hendrian, Yohei Ueki, Ryo Yoshinaka, and Ayumi Shinohara. Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm. Acta Informatica, 61(4):415–444, 2024. doi:10.1007/S00236-024-00464-W.
[18] Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka, and Ayumi Shinohara. Parallel algorithm for pattern matching problems under substring consistent equivalence relations. In 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022,, pages 28:1–28:21, 2022. doi:10.4230/LIPIcs.CPM.2022.28.
[19] Natsumi Kikuchi, Diptarama Hendrian, Ryo Yoshinaka, and Ayumi Shinohara. Computing covers under substring consistent equivalence relations. In String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, pages 131–146, 2020. doi:10.1007/978-3-030-59212-7_10.
[20] Sung-Hwan Kim and Hwan-Gue Cho. A compact index for Cartesian tree matching. In 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, pages 18:1–18:19, 2021. doi:10.4230/LIPIcs.CPM.2021.18.
[21] Sungmin Kim and Yo-Sub Han. Approximate Cartesian tree pattern matching. Theor. Comput. Sci., 1056:115506, 2025. doi:10.1016/J.TCS.2025.115506.
[22] Youngho Kim, Munseong Kang, Joong Chae Na, and Jeong Seop Sim. Order-preserving pattern matching with scaling. Inf. Process. Lett., 180:106333, 2023. doi:10.1016/J.IPL.2022.106333.
[23] Yoshiaki Matsuoka, Takahiro Aoki, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Generalized pattern matching and periodicity under substring consistent equivalence relations. Theor. Comput. Sci., 656:225–233, 2016. doi:10.1016/J.TCS.2016.02.017.
[24] Takuya Mieno, Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Computing maximal palindromes in non-standard matching models. Inf. Comput., 304:105283, 2025. doi:10.1016/J.IC.2025.105283.
[25] Temma Nakamura, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Order preserving pattern matching on trees and dags. In String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, pages 271–277. Springer, 2017. doi:10.1007/978-3-319-67428-5_23.
[26] Akio Nishimoto, Noriki Fujisato, Yuto Nakashima, and Shunsuke Inenaga. Position heaps for Cartesian tree matching on strings and tries. In String Processing and Information Retrieval - 28th International Symposium, SPIRE 2021, pages 241–254, 2021. doi:10.1007/978-3-030-86692-1_20.
[27] Tsubasa Oizumi, Takeshi Kai, Takuya Mieno, Shunsuke Inenaga, and Hiroki Arimura. Cartesian tree subsequence matching. In 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, pages 14:1–14:18, 2022. doi:10.4230/LIPIcs.CPM.2022.14.
[28] Eric M. Osterkamp and Dominik Köppl. Extending the Burrows-Wheeler transform for Cartesian tree matching and constructing it. In 36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025, pages 26:1–26:17, 2025. doi:10.4230/LIPIcs.CPM.2025.26.
[29] Sung Gwan Park, Magsarjav Bataa, Amihood Amir, Gad M. Landau, and Kunsoo Park. Finding patterns and periods in Cartesian tree matching. Theoretical Computer Science, 845:181–197, December 2020. doi:10.1016/J.TCS.2020.09.014.
[30] Luís M. S. Russo, Diogo M. Costa, Rui Henriques, Hideo Bannai, and Alexandre P. Francisco. Order-preserving pattern matching indeterminate strings. Inf. Comput., 289(Part):104924, 2022. doi:10.1016/J.IC.2022.104924.
[31] Siwoo Song, Geonmo Gu, Cheol Ryu, Simone Faro, Thierry Lecroq, and Kunsoo Park. Fast algorithms for single and multiple pattern Cartesian tree matching. Theor. Comput. Sci., 849:47–63, 2021. doi:10.1016/J.TCS.2020.10.009.
[32] Taketo Tsujimoto, Hiroki Shibata, Takuya Mieno, Yuto Nakashima, and Shunsuke Inenaga. Computing longest common subsequence under Cartesian tree matching model. In Combinatorial Algorithms - 35th International Workshop, IWOCA 2024, pages 369–381. Springer, 2024. doi:10.1007/978-3-031-63021-7_28.

[bib.bib1] [1] Bastien Auvray, Julien David, Samah Ghazawi, Richard Groult, Gad M. Landau, and Thierry Lecroq. Approximate Cartesian tree matching with one difference. CoRR, abs/2505.09236, 2025. doi:10.48550/arXiv.2505.09236.

[bib.bib2] [2] Michael A. Bender, Martin Farach-Colton, Giridhar Pemmasani, Steven Skiena, and Pavel Sumazin. Lowest common ancestors in trees and directed acyclic graphs. J. Algorithms, 57(2):75–94, 2005. doi:10.1016/J.JALGOR.2005.08.001.

[bib.bib3] [3] Dany Breslauer and Zvi Galil. Finding all periods and initial palindromes of a string in parallel. Algorithmica, 14(4):355–366, 1995. doi:10.1007/BF01294132.

[bib.bib4] [4] Karl Bringmann, Marvin Künnemann, and Philip Wellnitz. Few matches or almost periodicity: Faster pattern matching with mismatches in compressed texts. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 1126–1145. SIAM, 2019. doi:10.1137/1.9781611975482.69.

[bib.bib5] [5] Domenico Cantone, Simone Faro, and M. Oguzhan Külekci. The order-preserving pattern matching problem in practice. Discret. Appl. Math., 274:11–25, 2020. doi:10.1016/J.DAM.2018.10.023.

[bib.bib6] [6] Panagiotis Charalampopoulos, Tomasz Kociumaka, and Philip Wellnitz. Faster approximate pattern matching: A unified approach. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, pages 978–989. IEEE, 2020. doi:10.1109/FOCS46700.2020.00095.

[bib.bib7] [7] Tamanna Chhabra, Simone Faro, M. Oguzhan Külekci, and Jorma Tarhio. Engineering order-preserving pattern matching with SIMD parallelism. Softw. Pract. Exp., 47(5):731–739, 2017. doi:10.1002/SPE.2433.

[bib.bib8] [8] Sukhyeun Cho, Joong Chae Na, Kunsoo Park, and Jeong Seop Sim. A fast algorithm for order-preserving pattern matching. Inf. Process. Lett., 115(2):397–402, 2015. doi:10.1016/J.IPL.2014.10.018.

[bib.bib9] [9] Gianni Decaroli, Travis Gagie, and Giovanni Manzini. A compact index for order-preserving pattern matching. Softw. Pract. Exp., 49(6):1041–1051, 2019. doi:10.1002/SPE.2694.

[bib.bib10] [10] Erik D. Demaine, Gad M. Landau, and Oren Weimann. On Cartesian trees and range minimum queries. Algorithmica, 68(3):610–625, 2014. doi:10.1007/S00453-012-9683-X.

[bib.bib11] [11] Nathan J. Fine and Herbert S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 16(1):109–114, 1965. doi:10.2307/2034009.

[bib.bib12] [12] Johannes Fischer and Volker Heun. Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput., 40(2):465–492, 2011. doi:10.1137/090779759.

[bib.bib13] [13] Arnab Ganguly, Wing-Kai Hon, Kunihiko Sadakane, Rahul Shah, Sharma V. Thankachan, and Yilin Yang. Space-efficient dictionaries for parameterized and order-preserving pattern matching. In 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016, pages 2:1–2:12, 2016. doi:10.4230/LIPIcs.CPM.2016.2.

[bib.bib14] [14] Pawel Gawrychowski, Samah Ghazawi, and Gad M. Landau. On indeterminate strings matching. In 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, pages 14:1–14:14, 2020. doi:10.4230/LIPIcs.CPM.2020.14.

[bib.bib15] [15] Pawel Gawrychowski and Przemyslaw Uznanski. Order-preserving pattern matching with k mismatches. Theor. Comput. Sci., 638:136–144, 2016. doi:10.1016/J.TCS.2015.08.022.

[bib.bib16] [16] Diptarama Hendrian. Generalized dictionary matching under substring consistent equivalence relations. In WALCOM: Algorithms and Computation - 14th International Conference, WALCOM 2020, pages 120–132, 2020. doi:10.1007/978-3-030-39881-1_11.

[bib.bib17] [17] Davaajav Jargalsaikhan, Diptarama Hendrian, Yohei Ueki, Ryo Yoshinaka, and Ayumi Shinohara. Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm. Acta Informatica, 61(4):415–444, 2024. doi:10.1007/S00236-024-00464-W.

[bib.bib18] [18] Davaajav Jargalsaikhan, Diptarama Hendrian, Ryo Yoshinaka, and Ayumi Shinohara. Parallel algorithm for pattern matching problems under substring consistent equivalence relations. In 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022,, pages 28:1–28:21, 2022. doi:10.4230/LIPIcs.CPM.2022.28.

[bib.bib19] [19] Natsumi Kikuchi, Diptarama Hendrian, Ryo Yoshinaka, and Ayumi Shinohara. Computing covers under substring consistent equivalence relations. In String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, pages 131–146, 2020. doi:10.1007/978-3-030-59212-7_10.

[bib.bib20] [20] Sung-Hwan Kim and Hwan-Gue Cho. A compact index for Cartesian tree matching. In 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, pages 18:1–18:19, 2021. doi:10.4230/LIPIcs.CPM.2021.18.

[bib.bib21] [21] Sungmin Kim and Yo-Sub Han. Approximate Cartesian tree pattern matching. Theor. Comput. Sci., 1056:115506, 2025. doi:10.1016/J.TCS.2025.115506.

[bib.bib22] [22] Youngho Kim, Munseong Kang, Joong Chae Na, and Jeong Seop Sim. Order-preserving pattern matching with scaling. Inf. Process. Lett., 180:106333, 2023. doi:10.1016/J.IPL.2022.106333.

[bib.bib23] [23] Yoshiaki Matsuoka, Takahiro Aoki, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Generalized pattern matching and periodicity under substring consistent equivalence relations. Theor. Comput. Sci., 656:225–233, 2016. doi:10.1016/J.TCS.2016.02.017.

[bib.bib24] [24] Takuya Mieno, Mitsuru Funakoshi, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Computing maximal palindromes in non-standard matching models. Inf. Comput., 304:105283, 2025. doi:10.1016/J.IC.2025.105283.

[bib.bib25] [25] Temma Nakamura, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Order preserving pattern matching on trees and dags. In String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, pages 271–277. Springer, 2017. doi:10.1007/978-3-319-67428-5_23.

[bib.bib26] [26] Akio Nishimoto, Noriki Fujisato, Yuto Nakashima, and Shunsuke Inenaga. Position heaps for Cartesian tree matching on strings and tries. In String Processing and Information Retrieval - 28th International Symposium, SPIRE 2021, pages 241–254, 2021. doi:10.1007/978-3-030-86692-1_20.

[bib.bib27] [27] Tsubasa Oizumi, Takeshi Kai, Takuya Mieno, Shunsuke Inenaga, and Hiroki Arimura. Cartesian tree subsequence matching. In 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, pages 14:1–14:18, 2022. doi:10.4230/LIPIcs.CPM.2022.14.

[bib.bib28] [28] Eric M. Osterkamp and Dominik Köppl. Extending the Burrows-Wheeler transform for Cartesian tree matching and constructing it. In 36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025, pages 26:1–26:17, 2025. doi:10.4230/LIPIcs.CPM.2025.26.

[bib.bib29] [29] Sung Gwan Park, Magsarjav Bataa, Amihood Amir, Gad M. Landau, and Kunsoo Park. Finding patterns and periods in Cartesian tree matching. Theoretical Computer Science, 845:181–197, December 2020. doi:10.1016/J.TCS.2020.09.014.

[bib.bib30] [30] Luís M. S. Russo, Diogo M. Costa, Rui Henriques, Hideo Bannai, and Alexandre P. Francisco. Order-preserving pattern matching indeterminate strings. Inf. Comput., 289(Part):104924, 2022. doi:10.1016/J.IC.2022.104924.

[bib.bib31] [31] Siwoo Song, Geonmo Gu, Cheol Ryu, Simone Faro, Thierry Lecroq, and Kunsoo Park. Fast algorithms for single and multiple pattern Cartesian tree matching. Theor. Comput. Sci., 849:47–63, 2021. doi:10.1016/J.TCS.2020.10.009.

[bib.bib32] [32] Taketo Tsujimoto, Hiroki Shibata, Takuya Mieno, Yuto Nakashima, and Shunsuke Inenaga. Computing longest common subsequence under Cartesian tree matching model. In Combinatorial Algorithms - 35th International Workshop, IWOCA 2024, pages 369–381. Springer, 2024. doi:10.1007/978-3-031-63021-7_28.

Approximate Cartesian Tree Matching with Substitutions

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Approximate Cartesian tree matching.

Our contributions.

Theorem 1.

Technical overview.

Other related work.

2 Preliminaries

Lemma 2 (Periodicity Lemma (weak version) [11]).

Cartesian Trees

Definition 3.

Definition 4.

Fact 5.

Lemma 6 ([29]).

Lemma 7 ([29]).

Fact 8 (Theorem 2, [29]).

Lemma 9 ([29, Theorem 1]).

3 Cartesian Periodicity

Definition 10 ([23]).

Lemma 11.

Proof.

Definition 12.

▶ Remark 13.

Lemma 14.

Proof.

Lemma 15.

Proof.

Fact 16.

Lemma 17.

Proof.

Corollary 18.

Proof.

Lemma 19.

Proof.

Definition 20.

Example 21.

Lemma 22.

Proof.

Claim 23.

Proof.

4 Approximate CT-Matching with Substitutions

Lemma 24 (see [21]).

4.1 Analysing the Pattern

Definition 25.

Lemma 26.

Proof.

4.2 The Aperiodic Case

Lemma 27.

Proof.

Lemma 28.

Proof.

4.3 The Periodic Case

Lemma 29.

Proof.

Lemma 30.

Proof.

Lemma 31.

Proof.

Claim 32.

Claim 33.

Proof of Claim 32.

Proof of Claim 33.

Lemma 34 (analogue of Lemma 31).

Lemma 35.

Proof.

Case I: Enough blocks accumulated in at least one direction.

Case II: The pattern is almost CT-block-periodic.

Claim 36.

Proof.

Approximate Cartesian Tree Matching
with Substitutions

$\blacktriangleright$ Remark 13.