Internal Pattern Matching Queries in a Text and Applications
SIAM Journal on Computing · 31.10.2024 · 53 (5) · 1524-1577
DOI: 10.1137/23m1567618 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 14.10.2024. Verfasst von Tomasz Kociumaka und 3 weiteren Autor:innen. Die Arbeit wurde bisher 12-mal zitiert (Crossref) und nennt 115 Literaturangaben. Gefördert von: Narodowe Centrum Nauki.
Abstract (Originalsprache)
We consider several types of internal queries, that is, questions about fragments of a given text [Formula: see text] specified in constant space by their locations in [Formula: see text]. Our main result is an optimal data structure for internal pattern matching (IPM) queries, which, given two fragments [Formula: see text] and [Formula: see text], ask for a representation of all fragments contained in [Formula: see text] and matching [Formula: see text] exactly. This problem can be viewed as an internal version of the fundamental exact pattern matching problem: We are looking for exact occurrences of one substring of [Formula: see text] within another substring of [Formula: see text]. Our data structure answers IPM queries in time proportional to the quotient [Formula: see text] of the fragments’ lengths, which is required due to the worst-case information content of the output. If [Formula: see text] is a text of length [Formula: see text] over an integer alphabet of size [Formula: see text], then our data structure occupies [Formula: see text] machine words (that is, [Formula: see text] bits) and admits an [Formula: see text]-time construction algorithm. We also show how to use IPM queries for answering internal queries corresponding to other classic string processing problems. Among others, we derive optimal data structures reporting the periods of a fragment and testing the cyclic equivalence of two fragments. Since the publication of the conference version of this paper [Kociumaka et al., Internal pattern matching queries in a text and applications, SODA 2015], IPM queries have found numerous further applications, following the path paved by the classic longest common extension (LCE) queries of Landau and Vishkin [ J. Comput. System Sci., 37 (1988), pp. 63–78]. In particular, IPM queries have been implemented in grammar-compressed and dynamic settings and, along with LCE queries, constitute elementary operations of the [Formula: see text] model, developed by Charalampopoulos, Kociumaka, and Wellnitz [ Faster approximate pattern matching: A unified approach, FOCS 2020] to design approximate pattern matching algorithms that work in multiple settings. All our algorithms are deterministic, whereas the data structure in the conference version of the paper only admits a randomized construction in [Formula: see text] expected time. To achieve this, we provide a novel construction of string synchronizing sets of Kempa and Kociumaka [ String synchronizing sets: Sublinear-time BWT construction and optimal LCE data structure, STOC 2019]. Our method, based on a new restricted version of the recompression technique of Jeż [ J. ACM, 63 (2016), pp. 4:1–4:51], yields a hierarchy of [Formula: see text] string synchronizing sets covering the whole spectrum of the fragments’ lengths.
Förderung
- Narodowe Centrum Nauki
Zitieren
APA
Kociumaka, T., Radoszewski, J., Rytter, W., & Waleń, T. (2024). Internal Pattern Matching Queries in a Text and Applications. SIAM Journal on Computing, 53(5), 1524-1577. https://doi.org/10.1137/23m1567618
Vancouver
Kociumaka T, Radoszewski J, Rytter W, Waleń T. Internal Pattern Matching Queries in a Text and Applications. SIAM Journal on Computing. 2024;53(5):1524-1577. doi:10.1137/23m1567618
BibTeX
@article{Kociumaka2024,
author = {Kociumaka, Tomasz and Radoszewski, Jakub and Rytter, Wojciech and Waleń, Tomasz},
title = {Internal Pattern Matching Queries in a Text and Applications},
journal = {SIAM Journal on Computing},
year = {2024},
volume = {53},
number = {5},
pages = {1524--1577},
doi = {10.1137/23m1567618}
}
EUVIMED