  Cartesian tree pattern matching consists of finding all the factors of a text
that have the same Cartesian tree than a given pattern. There already exist
theoretical and practical solutions for the exact case. In this paper, we
propose the first algorithm for solving approximate Cartesian tree pattern
matching. We consider Cartesian tree pattern matching with one swap: given a
pattern of length m and a text of length n we present two algorithms that find
all the factors of the text that have the same Cartesian tree of the pattern
after one transposition of two adjacent symbols. The first algorithm uses a
characterization of a linear representation of the Cartesian trees called
parent-distance after one swap and runs in time Theta(mn) using Theta(m) space.
The second algorithm generates all the parent-distance tables of sequences that
have the same Cartesian tree than the pattern after one swap. It runs in time
O((m^2 + n)log m) and has O(m^2) space complexity.
