Document Open Access Logo

Cartesian Tree Subsequence Matching

Authors Tsubasa Oizumi, Takeshi Kai, Takuya Mieno , Shunsuke Inenaga , Hiroki Arimura

PDF

File

Thumbnail PDF
PDF
LIPIcs.CPM.2022.14.pdf
  • Filesize: 1.23 MB
  • 18 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Pattern matching
Keywords
  • string algorithms
  • pattern matching
  • Cartesian tree subsequence matching
  • order preserving matching
  • episode matching

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Park et al. [TCS 2020] observed that the similarity between two (numerical) strings can be captured by the Cartesian trees: The Cartesian tree of a string is a binary tree recursively constructed by picking up the smallest value of the string as the root of the tree. Two strings of equal length are said to Cartesian-tree match if their Cartesian trees are isomorphic. Park et al. [TCS 2020] introduced the following Cartesian tree substring matching (CTMStr) problem: Given a text string T of length n and a pattern string of length m, find every consecutive substring S = T[i..j] of a text string T such that S and P Cartesian-tree match. They showed how to solve this problem in Õ(n+m) time. In this paper, we introduce the Cartesian tree subsequence matching (CTMSeq) problem, that asks to find every minimal substring S = T[i..j] of T such that S contains a subsequence S' which Cartesian-tree matches P. We prove that the CTMSeq problem can be solved efficiently, in O(m n p(n)) time, where p(n) denotes the update/query time for dynamic predecessor queries. By using a suitable dynamic predecessor data structure, we obtain O(mn log log n)-time and O(n log m)-space solution for CTMSeq. This contrasts CTMSeq with closely related order-preserving subsequence matching (OPMSeq) which was shown to be NP-hard by Bose et al. [IPL 1998].

Cite As Get BibTex

Tsubasa Oizumi, Takeshi Kai, Takuya Mieno, Shunsuke Inenaga, and Hiroki Arimura. Cartesian Tree Subsequence Matching. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CPM.2022.14

Author Details

Tsubasa Oizumi
  • Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Japan
Takeshi Kai
  • Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Japan
Takuya Mieno
  • Faculty of Information Science and Technology, Hokkaido University, Sapporo, Japan
Shunsuke Inenaga
  • Department of Informatics, Kyushu University, Fukuoka, Japan
  • RESTO, Japan Science and Technology Agency, Kawaguchi, Japan
Hiroki Arimura
  • Faculty of Information Science and Technology, Hokkaido University, Sapporo, Japan

Funding

  • Mieno, Takuya: JSPS KAKENHI Grant Number JP20J11983.
  • Inenaga, Shunsuke: JST PRESTO Grant Number JPMJPR1922.
  • Arimura, Hiroki: JSPS KAKENHI Grant Number 20H00595, JST CREST Grant Number JPMJCR18K3.

Acknowledgements

The authors thank the anonymous referees for drawing our attention to reference [Pawel Gawrychowski et al., 2020].

References

  1. Brenda S. Baker. A theory of parameterized pattern matching: algorithms and applications. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pages 71-80. ACM, 1993. URL: https://doi.org/10.1145/167088.167115.
  2. Brenda S. Baker. Parameterized pattern matching: Algorithms and applications. J. Comput. Syst. Sci., 52(1):28-42, 1996. URL: https://doi.org/10.1006/jcss.1996.0003.
  3. Philip Bille, Inge Li Gørtz, Shay Mozes, Teresa Anna Steiner, and Oren Weimann. A conditional lower bound for episode matching. CoRR, abs/2108.08613, 2021. Google Scholar
  4. Prosenjit Bose, Jonathan F. Buss, and Anna Lubiw. Pattern matching for permutations. Inf. Process. Lett., 65(5):277-283, 1998. URL: https://doi.org/10.1016/S0020-0190(97)00209-3.
  5. Sukhyeun Cho, Joong Chae Na, Kunsoo Park, and Jeong Seop Sim. A fast algorithm for order-preserving pattern matching. Inf. Process. Lett., 115(2):397-402, 2015. URL: https://doi.org/10.1016/j.ipl.2014.10.018.
  6. Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. Order-preserving indexing. Theor. Comput. Sci., 638:122-135, 2016. URL: https://doi.org/10.1016/j.tcs.2015.06.050.
  7. Gautam Das, Rudolf Fleischer, Leszek Gasieniec, Dimitrios Gunopulos, and Juha Kärkkäinen. Episode matching. In Alberto Apostolico and Jotun Hein, editors, Combinatorial Pattern Matching, 8th Annual Symposium, CPM 97, Aarhus, Denmark, June 30 - July 2, 1997, Proceedings, volume 1264 of Lecture Notes in Computer Science, pages 12-27. Springer, 1997. URL: https://doi.org/10.1007/3-540-63220-4_46.
  8. Noriki Fujisato, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. The parameterized suffix tray. In Tiziana Calamoneri and Federico Corò, editors, Algorithms and Complexity - 12th International Conference, CIAC 2021, Virtual Event, May 10-12, 2021, Proceedings, volume 12701 of Lecture Notes in Computer Science, pages 258-270. Springer, 2021. URL: https://doi.org/10.1007/978-3-030-75242-2_18.
  9. Harold N. Gabow, Jon Louis Bentley, and Robert Endre Tarjan. Scaling and related techniques for geometry problems. In Richard A. DeMillo, editor, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30 - May 2, 1984, Washington, DC, USA, pages 135-143. ACM, 1984. URL: https://doi.org/10.1145/800057.808675.
  10. Pawel Gawrychowski, Samah Ghazawi, and Gad M. Landau. On indeterminate strings matching. In Proc. 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020), volume 161 of LIPIcs, pages 14:1-14:14, 2020. Google Scholar
  11. Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput., 13(2):338-355, 1984. URL: https://doi.org/10.1137/0213024.
  12. Rui Henriques, Alexandre P. Francisco, Luís M. S. Russo, and Hideo Bannai. Order-preserving pattern matching indeterminate strings. In Annual Symposium on Combinatorial Pattern Matching (CPM 2018), volume 105 of LIPIcs, pages 2:1-2:15, 2018. Google Scholar
  13. Christoph M. Hoffmann and Michael J. O'Donnell. Pattern matching in trees. J. ACM, 29(1):68-95, 1982. URL: https://doi.org/10.1145/322290.322295.
  14. Ramana M. Idury and Alejandro A. Schäffer. Multiple matching of parametrized patterns. Theor. Comput. Sci., 154(2):203-224, 1996. URL: https://doi.org/10.1016/0304-3975(94)00270-3.
  15. Orgad Keller, Tsvi Kopelowitz, and Moshe Lewenstein. On the longest common parameterized subsequence. Theor. Comput. Sci., 410(51):5347-5353, 2009. URL: https://doi.org/10.1016/j.tcs.2009.09.011.
  16. Jinil Kim, Peter Eades, Rudolf Fleischer, Seok-Hee Hong, Costas S. Iliopoulos, Kunsoo Park, Simon J. Puglisi, and Takeshi Tokuyama. Order-preserving matching. Theor. Comput. Sci., 525:68-79, 2014. URL: https://doi.org/10.1016/j.tcs.2013.10.006.
  17. Marcin Kubica, Tomasz Kulczynski, Jakub Radoszewski, Wojciech Rytter, and Tomasz Walen. A linear time algorithm for consecutive permutation pattern matching. Inf. Process. Lett., 113(12):430-433, 2013. URL: https://doi.org/10.1016/j.ipl.2013.03.015.
  18. Yoshiaki Matsuoka, Takahiro Aoki, Shunsuke Inenaga, Hideo Bannai, and Masayuki Takeda. Generalized pattern matching and periodicity under substring consistent equivalence relations. Theor. Comput. Sci., 656:225-233, 2016. URL: https://doi.org/10.1016/j.tcs.2016.02.017.
  19. Juan Mendivelso, Sharma V. Thankachan, and Yoan J. Pinzón. A brief history of parameterized matching problems. Discret. Appl. Math., 274:103-115, 2020. URL: https://doi.org/10.1016/j.dam.2018.07.017.
  20. Sung Gwan Park, Magsarjav Bataa, Amihood Amir, Gad M. Landau, and Kunsoo Park. Finding patterns and periods in Cartesian tree matching. Theor. Comput. Sci., 845:181-197, 2020. URL: https://doi.org/10.1016/j.tcs.2020.09.014.
  21. Siwoo Song, Geonmo Gu, Cheol Ryu, Simone Faro, Thierry Lecroq, and Kunsoo Park. Fast algorithms for single and multiple pattern Cartesian tree matching. Theor. Comput. Sci., 849:47-63, 2021. URL: https://doi.org/10.1016/j.tcs.2020.10.009.
  22. Peter van Emde Boas. Preserving order in a forest in less than logarithmic time and linear space. Inf. Process. Lett., 6(3):80-82, 1977. URL: https://doi.org/10.1016/0020-0190(77)90031-X.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact