  We introduce a new metric of match, called Cartesian tree matching, which
means that two strings match if they have the same Cartesian trees. Based on
Cartesian tree matching, we define single pattern matching for a text of length
n and a pattern of length m, and multiple pattern matching for a text of length
n and k patterns of total length m. We present an O(n+m) time algorithm for
single pattern matching, and an O((n+m) log k) deterministic time or O(n+m)
randomized time algorithm for multiple pattern matching. We also define an
index data structure called Cartesian suffix tree, and present an O(n)
randomized time algorithm to build the Cartesian suffix tree. Our efficient
algorithms for Cartesian tree matching use a representation of the Cartesian
tree, called the parent-distance representation.
