2026-08-16T08:14:12Z https://drops.dagstuhl.de/oai

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

LF Successor: Compact Space Indexing for Order-Isomorphic Pattern Matching Ganguly, Arnab Patel, Dhrumil Shah, Rahul Thankachan, Sharma V. Succinct data structures Pattern Matching Two strings are order isomorphic iff the relative ordering of their characters is the same at all positions. For a given text T[1,n] over an ordered alphabet of size σ, we can maintain an order-isomorphic suffix tree/array in O(nlog n) bits and support (order-isomorphic) pattern/substring matching queries efficiently. It is interesting to know if we can encode these structures in space close to the text’s size of nlogσ bits. We answer this question positively by presenting an O(nlog σ)-bit index that allows access to any entry in order-isomorphic suffix array (and its inverse array) in t_{SA} = {O}(log²n/logσ) time. For any pattern P given as a query, this index can count the number of substrings of T that are order-isomorphic to P (denoted by occ) in {O}((|P|logσ+t_{SA})log n) time using standard techniques. Also, it can report the locations of those substrings in additional O(occ ⋅ t_{SA}) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arnab Ganguly and Dhrumil Patel and Rahul Shah and Sharma V. Thankachan 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.71 urn:nbn:de:0030-drops-141400 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.71 eng https://creativecommons.org/licenses/by/4.0/legalcode