Image de couverture de livre

Space-Efficient k-Mismatch Text Indexes

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Kociumaka, Tomasz, Radoszewski, Jakub
Format:	Preprint
Publié:	2025
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Faster Algorithms for Longest Common Substring
par: Charalampopoulos, Panagiotis, et autres
Publié: (2021)

Fast Computation of $k$-Runs, Parameterized Squares, and Other Generalised Squares
par: Nakashima, Yuto, et autres
Publié: (2025)

Approximate Circular Pattern Matching
par: Charalampopoulos, Panagiotis, et autres
Publié: (2022)

Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts
par: Duyster, Anouk, et autres
Publié: (2025)

Tight Lower Bounds for Central String Queries in Compressed Space
par: Kempa, Dominik, et autres
Publié: (2025)

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
par: Kempa, Dominik, et autres
Publié: (2023)

Space-Efficient Text Indexing with Mismatches using Function Inversion
par: Bibbens, Jackson, et autres
Publié: (2026)

Computing String Covers in Sublinear Time
par: Radoszewski, Jakub, et autres
Publié: (2024)

Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
par: Bathie, Gabriel, et autres
Publié: (2023)

Near-Optimal Property Testers for Pattern Matching
par: Jin, Ce, et autres
Publié: (2025)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
par: Kempa, Dominik, et autres
Publié: (2025)

Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime
par: Kociumaka, Tomasz, et autres
Publié: (2025)

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
par: Kempa, Dominik, et autres
Publié: (2025)

Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
par: Gorbachev, Egor, et autres
Publié: (2024)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
par: Kempa, Dominik, et autres
Publié: (2024)

Time-Optimal Construction of String Synchronizing Sets
par: Ellert, Jonas, et autres
Publié: (2026)

Random Access in Grammar-Compressed Strings: Optimal Trade-Offs in Almost All Parameter Regimes
par: Duyster, Anouk, et autres
Publié: (2026)

Counting Distinct Square Substrings in Sublinear Time
par: Charalampopoulos, Panagiotis, et autres
Publié: (2025)

Pattern Matching under Weighted Edit Distance
par: Charalampopoulos, Panagiotis, et autres
Publié: (2025)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
par: Boneh, Itai, et autres
Publié: (2025)

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
par: Gawrychowski, Paweł, et autres
Publié: (2024)

The Communication Complexity of Pattern Matching with Edits Revisited
par: Kociumaka, Tomasz, et autres
Publié: (2026)

Subsequence Covers of Words
par: Charalampopoulos, Panagiotis, et autres
Publié: (2025)

Approximate Circular Pattern Matching under Edit Distance
par: Charalampopoulos, Panagiotis, et autres
Publié: (2024)

Near-Optimal-Time Quantum Algorithms for Approximate Pattern Matching
par: Kociumaka, Tomasz, et autres
Publié: (2024)

On the Communication Complexity of Approximate Pattern Matching
par: Kociumaka, Tomasz, et autres
Publié: (2024)

Language Edit Distance & Scored Parsing: Faster Algorithms & Connection to Fundamental Graph Problems
par: Kociumaka, Tomasz, et autres
Publié: (2014)

Faster ED-String Matching with $k$ Mismatches
par: Gawrychowski, Paweł, et autres
Publié: (2025)

Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance
par: Das, Debarati, et autres
Publié: (2025)

Pattern Masking for Dictionary Matching
par: Charalampopoulos, Panagiotis, et autres
Publié: (2020)

On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches
par: Amir, Amihood, et autres
Publié: (2026)

Elastic-Degenerate String Comparison
par: Gabory, Esteban, et autres
Publié: (2024)

Optimal-Length Labeling Schemes and Fast Algorithms for k-gathering and k-broadcasting
par: Ganczorz, Adam, et autres
Publié: (2025)

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number
par: Casel, Katrin, et autres
Publié: (2019)

An Algorithmic Bridge Between Hamming and Levenshtein Distances
par: Goldenberg, Elazar, et autres
Publié: (2022)

Space-Efficient Indexes for Uncertain Strings
par: Gabory, Esteban, et autres
Publié: (2024)

Simple Quantum Algorithm for Approximate $k$-Mismatch Problem
par: Habib, Ruhan, et autres
Publié: (2025)

String Indexing for Top-$k$ Close Consecutive Occurrences
par: Bille, Philip, et autres
Publié: (2020)

Pattern Matching with Mismatches and Wildcards
par: Bathie, Gabriel, et autres
Publié: (2024)

Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text
par: Adudodla, Ankith Reddy, et autres
Publié: (2025)