Approximate Cartesian tree pattern matching
Sungmin Kim and Yo-Sub Han.
Published in Theoretical Computer Science, 2025.
Published in Theoretical Computer Science, 2025.
Definitions
Cartesian tree:
for a string over integer characters,
if the string is of length 0, it is the empty tree.
Otherwise, take the minimum integer as the root, and recursively build
the left and right subtrees using the prefix and suffix split by the minimum integer.
Approximate pattern matching under Cartesian tree equivalence:
find all substrings of a given text
that can be transformed into another string
with the same Cartesian tree as the given pattern
by applying at most a given number of edits.
Summary of results
- A $O(|w|^3|u|(|w|+|u|))$ time algorithm for computing the edit distance from $w$ to $u$
- A $O(|\texttt{T}|^3|\texttt{P}|t)$ time algorithm for the approximate pattern matching problem under Cartesian tree equivalence, where $t$ is the maximum number of edits
- A $O(|\texttt{T}||\texttt{P}|t)$ time algorithm for the approximate pattern matching problem under Cartesian tree equivalence when only substitutions are allowed
- An algorithm that computes the max-min convolution between two non-decreasing sequence of integers of length $m$ and $n$ in $O(m+n)$ time
Keywords
Cartesian tree, approximate pattern matching, dynamic programming, recurrence relation, max-min convolution