Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Fast Cartesian Tree Matching

Abstract : Cartesian tree matching is the problem of finding all substrings of a given text which have the same Cartesian trees as that of a given pattern. So far there is one linear-time solution for Cartesian tree matching, which is based on the KMP algorithm. We improve the running time of the previous solution by introducing new representations. We present the framework of a binary filtration method and an efficient verification technique for Cartesian tree matching. Any exact string matching algorithm can be used as a filtration for Cartesian tree matching on our framework. We also present a SIMD solution for Cartesian tree matching suitable for short patterns. By experiments we show that known string matching algorithms combined on our framework of binary filtration and efficient verification produce algorithms of good performances for Cartesian tree matching.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas
Contributor : Thierry Lecroq <>
Submitted on : Wednesday, August 21, 2019 - 11:21:00 PM
Last modification on : Tuesday, October 1, 2019 - 4:17:35 PM

Links full text


  • HAL Id : hal-02268954, version 1
  • ARXIV : 1908.04937


Siwoo Song, Cheol Ryu, Simone Faro, Thierry Lecroq, Kunsoo Park. Fast Cartesian Tree Matching. 2019. ⟨hal-02268954⟩



Record views