2026-08-17T18:57:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17346 2024-03-06T10:59:31Z ddc:004 open_access

Simple Order-Isomorphic Matching Index with Expected Compact Space Kim, Sung-Hwan Cho, Hwan-Gue Compact Data Structure String Matching Order-Preserving Matching Suffix Array FM-index Binary Search Tree In this paper, we present a novel indexing method for the order-isomorphic pattern matching problem (also known as order-preserving pattern matching, or consecutive permutation matching), in which two equal-length strings are defined to match when X[i] < X[j] iff Y[i] < Y[j] for 0 ≤ i,j < |X|. We observe an interesting relation between the order-isomorphic matching and the insertion process of a binary search tree, based on which we propose a data structure which not only has a concise structure comprised of only two wavelet trees but also provides a surprisingly simple searching algorithm. In the average case analysis, the proposed method requires 𝒪(R(T)) bits, and it is capable of answering a count query in 𝒪(R(P)) time, and reporting an occurrence in 𝒪(lg |T|) time, where T and P are the text and the pattern string, respectively; for a string X, R(X) is the total time taken for the construction of the binary search tree by successively inserting the keys X[|X|-1],⋯,X[0] at the root, and its expected value is 𝒪(|X|lgσ) where σ is the alphabet size. Furthermore, the proposed method can be viewed as a generalization of some other methods including several heuristics and restricted versions described in previous studies in the literature. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sung-Hwan Kim and Hwan-Gue Cho 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.61 urn:nbn:de:0030-drops-173466 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.61 eng https://creativecommons.org/licenses/by/4.0/legalcode