Example

$ \def\sa#1{\tt{#1}} \def\dd{\dot{}\dot{}} \def\CT{\mathcal{CT}} $ The following tree is the Cartesian tree of

$i$	0	1	2	3	4	5	6	7	8
$x[i]$	3	1	6	4	8	6	7	5	9

With $$x = \sa{3}\; \sa{1}\; \sa{6}\; \sa{4}\; \sa{8}\; \sa{6}\; \sa{7}\; \sa{5}\; \sa{9}$$ and $$y = \sa{10}\; \sa{12}\; \sa{16}\; \underline{\sa{15}\; \sa{6}\; \sa{14}\; \sa{9}\; \sa{12}\; \sa{11}\; \sa{14}\; \sa{9}\; \sa{17}}\; \sa{12}\; \sa{10}\; \sa{12}$$ $\CT(x)=\CT(y[3\dd 11])$ and this is the only position where it occurs.

Additional Problem 21: Cartesian Tree Patterns

$ \def\PD{\mathit{PD}} $

Searching time series or list of values for patterns representing specific fluctuations of the values requires a redefinition of the notion of pattern.

In the problem we consider words drawn from a linear-sortable alphabet $\Sigma$ of integers.

Let $x$ be a word of length $m$. The Cartesian Tree $\CT(x)$ of $x$ is the binary tree where:

the root corresponds to the index $i$ of the minimal element of $x$ (if there are several occurrences of the minimal element, the leftmost one is chosen);
the left subtree of the root corresponds to the Cartesian Tree of $x[0\dd i-1]$;
the right subtree of the root corresponds to the Cartesian Tree of $x[i+1\dd m-1]$.

Design a linear time and space algorithm that, given a word $x\in\Sigma^*$, builds the Cartesian tree of $x$ online.

Consider only the nodes on the right path of the tree.

The Cartesian tree pattern-matching problem is naturally defined as follows: given a pattern $x\in\Sigma^*$ and a text $y\in\Sigma^*$, find all the factors of $y$ that have the same Cartesian tree as $x$. More formally, find all $j$ such that $0\le j \le n-m$ and $\CT(x) = \CT(y[j\dd j+m-1])$.

Design a linear-time algorithm for the Cartesian tree pattern-matching.

Find a linear representation of Cartesian trees and design a notion of border table (see Problem 19) adequate to the problem.

References

S. G. Park, A. Amir, G. M. Landau and K. Park, Cartesian Tree Matching and Indexing, In: N. Pisanti and S. P. Pissis editors, Proceedings of the 30th Annual Symposium on Combinatorial Pattern Matching (CPM),Pisa, Italy, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, LIPIcs 128: 16:1-16:14, 2019.
S. Song, G. Gu, C. Ryu, S. Faro, T. Lecroq and K. Park, Fast algorithms for single and multiple pattern Cartesian tree matching, Theor. Comput. Sci. 849: 47-63, 2021.
J. Vuillemin, A Unifying Look at Data Structures}, Commun. ACM 23(4): 229-239, 1980.

125 Problems in Text Algorithms

Example

Additional Problem 21: Cartesian Tree Patterns

References