2026-09-05T07:00:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25933 2026-06-23T13:12:24Z ddc:004 open_access

Optimal Structure for Prefix-Substring Queries Gawrychowski, Paweł Manea, Florin Richardsen, Jonas Border Tree Prefix-Substring Query Data Structures The prefix-substring matching problem [Gu, Farach, and Beigel, SODA 1994] consists in preprocessing a string s of length n for the following queries: given a triple (i, j, k) ∈ {0, … , |s|}³ with 1 ≤ j ≤ k, representing a prefix s[1:i] and a substring s[j:k] of s, find the longest prefix of s that is a suffix of s[1:i]s[j:k]. This is an useful primitive in e.g. dynamic text indexing, compressed pattern matching, and pattern matching on block graphs. The border tree uses some basic periodicity properties to answer such queries in 𝒪(log n) time after 𝒪(n) time preprocessing of s. We design a linear-space structure that answers such queries in constant time after 𝒪(n) time preprocessing of s over a polynomial alphabet, which is worst-case optimal. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paweł Gawrychowski and Florin Manea and Jonas Richardsen 2026 Is Part Of LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2026.7 urn:nbn:de:0030-drops-259333 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.7 eng https://creativecommons.org/licenses/by/4.0/legalcode