2026-07-23T13:55:56Z https://drops.dagstuhl.de/oai

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

An Invertible Transform for Efficient String Matching in Labeled Digraphs Nellore, Abhinav Nguyen, Austin Thompson, Reid F. pattern matching string matching Burrows-Wheeler transform labeled graphs Let G = (V, E) be a digraph where each vertex is unlabeled, each edge is labeled by a character in some alphabet Ω, and any two edges with both the same head and the same tail have different labels. The powerset construction gives a transform of G into a weakly connected digraph G' = (V', E') that enables solving the decision problem of whether there is a walk in G matching an arbitrarily long query string q in time linear in |q| and independent of |E| and |V|. We show G is uniquely determined by G' when for every v_𝓁 ∈ V, there is some distinct string s_𝓁 on Ω such that v_𝓁 is the origin of a closed walk in G matching s_𝓁, and no other walk in G matches s_𝓁 unless it starts and ends at v_𝓁. We then exploit this invertibility condition to strategically alter any G so its transform G' enables retrieval of all t terminal vertices of walks in the unaltered G matching q in O(|q| + t log |V|) time. We conclude by proposing two defining properties of a class of transforms that includes the Burrows-Wheeler transform and the transform presented here. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Abhinav Nellore and Austin Nguyen and Reid F. Thompson 2021 Is Part Of LIPIcs, Volume 191, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2021.20 urn:nbn:de:0030-drops-139717 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2021.20 eng https://creativecommons.org/licenses/by/4.0/legalcode