License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2019.16
URN: urn:nbn:de:0030-drops-104879
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10487/
Go to the corresponding LIPIcs Volume Portal

Park, Sung Gwan ; Amir, Amihood ; Landau, Gad M. ; Park, Kunsoo

Cartesian Tree Matching and Indexing

pdf-format:
LIPIcs-CPM-2019-16.pdf (0.8 MB)

Abstract

We introduce a new metric of match, called Cartesian tree matching, which means that two strings match if they have the same Cartesian trees. Based on Cartesian tree matching, we define single pattern matching for a text of length n and a pattern of length m, and multiple pattern matching for a text of length n and k patterns of total length m. We present an O(n+m) time algorithm for single pattern matching, and an O((n+m) log k) deterministic time or O(n+m) randomized time algorithm for multiple pattern matching. We also define an index data structure called Cartesian suffix tree, and present an O(n) randomized time algorithm to build the Cartesian suffix tree. Our efficient algorithms for Cartesian tree matching use a representation of the Cartesian tree, called the parent-distance representation.

BibTeX - Entry

@InProceedings{park_et_al:LIPIcs:2019:10487,
  author =	{Sung Gwan Park and Amihood Amir and Gad M. Landau and Kunsoo Park},
  title =	{{Cartesian Tree Matching and Indexing}},
  booktitle =	{30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-103-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{128},
  editor =	{Nadia Pisanti and Solon P. Pissis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10487},
  URN =		{urn:nbn:de:0030-drops-104879},
  doi =		{10.4230/LIPIcs.CPM.2019.16},
  annote =	{Keywords: Cartesian tree matching, Pattern matching, Indexing, Parent-distance representation}
}

Keywords: Cartesian tree matching, Pattern matching, Indexing, Parent-distance representation
Collection: 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019)
Issue Date: 2019
Date of publication: 06.06.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI