Internal Pattern Matching Queries in a Text and Applications

DOI10.1137/1.9781611973730.36zbMath1371.68340arXiv1311.6235OpenAlexW2949583843MaRDI QIDQ5362985

Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen, Jakub Radoszewski

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

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

Related Items

Computing minimal and maximal suffixes of a substring, Universal Reconstruction of a String, Multidimensional period recovery, String Powers in Trees, On Maximal Unbordered Factors, Internal shortest absent word queries in constant time and linear space, Finding top-\(k\) longest palindromes in substrings, Finding the cyclic covers of a string, Internal masked prefix sums and its connection to fully internal measurement queries, The “Runs” Theorem, Unnamed Item, Near-optimal quantum algorithms for string problems, Period recovery of strings over the Hamming and edit distances, Unnamed Item, Dynamic and internal longest common substring, Efficient Computation of 2-Covers of a String., Practical Performance of Space Efficient Data Structures for Longest Common Extensions., Detecting One-Variable Patterns, Shortest covers of all cyclic shifts of a string, Unnamed Item, Unnamed Item, Maximal unbordered factors of random strings, Internal dictionary matching, Repetition Detection in a Dynamic String, Circular pattern matching with \(k\) mismatches, Two-dimensional maximal repetitions, Longest common substring made fully dynamic, Quasi-Linear-Time Algorithm for Longest Common Circular Factor, Elastic-Degenerate String Matching via Fast Matrix Multiplication