2026-08-17T21:14:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13969 2024-03-06T10:53:01Z ddc:004 open_access

A Compact Index for Cartesian Tree Matching Kim, Sung-Hwan Cho, Hwan-Gue String Matching Suffix Array FM-index Compact Index Cartesian Tree Matching Cartesian tree matching is a recently introduced string matching problem in which two strings match if their corresponding Cartesian trees are the same. It is considered appropriate to find patterns regarding their shapes especially in numerical time series data. While many related problems have been addressed, developing a compact index has received relatively less attention. In this paper, we present a 3n+o(n)-bit index that can count the number of occurrences of a Cartesian tree pattern in 𝒪(m) time where n and m are the text and pattern length. To the best of our knowledge, this work is the first 𝒪(n)-bit compact data structure for indexing for this problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sung-Hwan Kim and Hwan-Gue Cho 2021 Is Part Of LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2021.18 urn:nbn:de:0030-drops-139699 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.18 eng https://creativecommons.org/licenses/by/4.0/legalcode