Scholarlink

In this paper, we introduce the notion of Cartesian Forest, which generalizes Cartesian Trees, in order to deal with duplicates in ordered sequences. We show that algorithms that solve both exact and approximate Cartesian Tree Matching can be adapted to solve Cartesian Forest Matching in linear time in the worst-case for exact matching and linear time on average for approximate matching. We adapt the notion of Cartesian Tree Signature to Cartesian Forests. We also show a one-to-one correspondence between Cartesian Forests and Schröder Trees.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Cartesian Forest Matching

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Bastien Auvray,
  • Julien David,
  • Richard Groult,
  • Thierry Lecroq

摘要

In this paper, we introduce the notion of Cartesian Forest, which generalizes Cartesian Trees, in order to deal with duplicates in ordered sequences. We show that algorithms that solve both exact and approximate Cartesian Tree Matching can be adapted to solve Cartesian Forest Matching in linear time in the worst-case for exact matching and linear time on average for approximate matching. We adapt the notion of Cartesian Tree Signature to Cartesian Forests. We also show a one-to-one correspondence between Cartesian Forests and Schröder Trees.