Approximate Cartesian Tree Matching with Substitutions

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 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 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 CT (P). Our algorithm runs in time 𝒪 (n √m ⋅ k^2. 5) for k ≤ m^1/5 and in time 𝒪 (nk⁵) for k ≥ m^1/5, thereby improving upon the state-of-the-art 𝒪 (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.