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<br/>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.<br/>To overcome this limitation, we consider the approximate setting, where the goal is to identify<br/>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 &gt; 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 O(n√m · k2.5 ) for k ≤ m1/5<br/>and in time O(nk5) for k ≥ m1/5<br/>, thereby improving upon the<br/>state-of-the-art O(nmk)-time algorithm of Kim and Han [TCS 2025] in the regime k = o(m1/4<br/>). <br/>On the way to our solution, we develop a toolbox of independent interest. First, we introduce a<br/>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<br/>periodicity in Cartesian trees