CLR cover

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:

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.