# 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.