2026-07-23T19:43:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23919 2026-02-09T06:23:58Z ddc:004 open_access

Circular Dictionary Matching Using Extended BWT Hon, Wing-Kai Shah, Rahul Thankachan, Sharma V. String algorithms Burrows-Wheeler transformation suffix trees succinct data structures The dictionary matching problem involves preprocessing a set of strings (patterns) into a data structure that efficiently identifies all occurrences of these patterns within a query string (text). In this work, we investigate a variation of this problem, termed circular dictionary matching, where the patterns are circular, meaning their cyclic shifts are also considered valid patterns. Such patterns naturally occur in areas such as bioinformatics and computational geometry. Based on the extended Burrows-Wheeler Transformation (eBWT), we design a space-efficient solution for this problem. Specifically, we show that a dictionary of d circular patterns of total length n can be indexed in nlog σ + O(n+dlog n+σ log n) bits of space and support circular dictionary matching on a query text T in O((|T|+occ)log n) time, where σ represents the size of the underlying alphabet and occ represents the output size. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Wing-Kai Hon and Rahul Shah and Sharma V. Thankachan 2025 Is Part Of OASIcs, Volume 131, The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday (2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.Manzini.11 urn:nbn:de:0030-drops-239195 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Manzini.11 eng https://creativecommons.org/licenses/by/4.0/legalcode