Approximate Cartesian tree pattern matching
Sungmin Kim and Yo-Sub Han.
Presented at DLT'24.
Presented at DLT'24.
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|)^2)$ time algorithm for computing the edit distance from $w$ to $u$
- A $O(|\texttt{T}|^3|\texttt{P}|t^2)$ 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^2)$ time algorithm for the approximate pattern matching problem under Cartesian tree equivalence when only substitutions are allowed
Note: improved algorithms are given in the journal version of the paper.
Keywords
Cartesian tree, approximate pattern matching, dynamic programming, recurrence relation