Internal pattern matching queries in a text and applications

DOI10.1137/1.9781611973730.36MaRDI QIDQ5362985zbMATH OpenOpenAlexFDO

Authors Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.6235

Mathematics Subject Classification ID

Data structures (68P05) Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: We consider several types of internal queries, that is, questions about fragments of a given text $T$ specified in constant space by their locations in $T$. Our main result is an optimal data structure for Internal Pattern Matching (IPM) queries which, given two fragments $x$ and $y$, ask for a representation of all fragments contained in $y$ and matching $x$ exactly; this problem can be viewed as an internal version of the Exact Pattern Matching problem. Our data structure answers IPM queries in time proportional to the quotient $|y|/|x|$ of fragments' lengths, which is required due to the information content of the output. If $T$ is a text of length $n$ over an integer alphabet of size $sigma$, then our data structure occupies $O(n/lo{g}_{s}igman)$ machine words (that is, $O(nlogsigma)$ bits) and admits an $O(n/lo{g}_{s}igman)$-time construction algorithm. We show the applicability of 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. IPM queries have already found numerous further applications, following the path paved by the classic Longest Common Extension (LCE) queries of Landau and Vishkin (JCSS, 1988). In particular, IPM queries have been implemented in grammar-compressed and dynamic settings and, along with LCE queries, constitute elementary operations of the PILLAR model, developed by Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020). On the way to our main result, we provide a novel construction of string synchronizing sets of Kempa and Kociumaka (STOC 2019). Our method, based on a new restricted version of the recompression technique of Je.z (J. ACM, 2016), yields a hierarchy of $O(logn)$ string synchronizing sets covering the whole spectrum of fragments' lengths.

Recommendations

• Internal dictionary matching
• Internal Quasiperiod Queries
• scientific article; zbMATH DE number 1438578
• scientific article; zbMATH DE number 1445383
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)

Cited in

(32)

• String Powers in Trees
• Longest common substring made fully dynamic
• Quasi-Linear-Time Algorithm for Longest Common Circular Factor
• scientific article; zbMATH DE number 7651171 (Why is no real title available?)
• Universal reconstruction of a string
• On maximal unbordered factors
• Efficient Computation of 2-Covers of a String.
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Computing minimal and maximal suffixes of a substring
• Finding the cyclic covers of a string
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Multidimensional period recovery
• Two-dimensional maximal repetitions
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Internal dictionary matching
• Dynamic and internal longest common substring
• Internal dictionary matching
• Two-dimensional maximal repetitions
• Internal pattern matching queries in a text and applications
• Near-optimal quantum algorithms for string problems
• Longest unbordered factor in quasilinear time
• Internal shortest absent word queries in constant time and linear space
• Shortest covers of all cyclic shifts of a string
• Internal Quasiperiod Queries
• Circular pattern matching with \(k\) mismatches
• Weighted edit distance computation: strings, trees, and Dyck
• The ``runs theorem
• Period recovery of strings over the Hamming and edit distances
• Repetition Detection in a Dynamic String
• scientific article; zbMATH DE number 1445383 (Why is no real title available?)
• Internal masked prefix sums and its connection to fully internal measurement queries
• Detecting one-variable patterns

This page was built for publication: Internal pattern matching queries in a text and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5362985)