2026-08-17T09:33:05Z https://drops.dagstuhl.de/oai

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

Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties Iliopoulos, Costas S. Radoszewski, Jakub string with don’t cares partial word indeterminate string longest common conservative prefix queries prefix array Strings with don't care symbols, also called partial words, and more general indeterminate strings are a natural representation of strings containing uncertain symbols. A considerable effort has been made to obtain efficient algorithms for pattern matching and periodicity detection in such strings. Among those, a number of algorithms have been proposed that behave well on random data, but still their worst-case running time is Theta(n^2). We present the first truly subquadratic-time solutions for a number of such problems on partial words that can also be adapted to indeterminate strings over a constant-sized alphabet. We show that $n$ longest common compatible prefix queries (which correspond to longest common extension queries in regular strings) can be answered on-line in O(n * sqrt(n * log(n)) time after O(n * sqrt(n * log(n))-time preprocessing. We also present O(n * sqrt(n * log(n))-time algorithms for computing the prefix array and two types of border array of a partial word. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Costas S. Iliopoulos and Jakub Radoszewski 2016 Is Part Of LIPIcs, Volume 54, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2016.8 urn:nbn:de:0030-drops-60842 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2016.8 eng https://creativecommons.org/licenses/by/3.0/legalcode