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.

Problem 145: Cartesian tree pattern-matching

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

In the problem we consider words drawn from a linear-sortable alphabet $\Sigma$ of integers. Let $x=x[0\dd m-1]$ be a word of length $m$. The Cartesian Tree $\CT(x)$ of $x$ is the binary tree in which:

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

The Cartesian tree pattern-matching problem is naturally defined as follows: given a pattern $x$ and a text $y$ of length $m$ and $n$ respectively, find all the factors of $y$ that have the same Cartesian tree as $x$.

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

Consider only the nodes on the rightmost paths of the tree.

Design a linear-time algorithm for the Cartesian tree pattern-matching related to a pattern $x$ and a text $y$ in $\Sigma^*$.

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

Problem 145: Cartesian tree pattern-matching

References