Cover Image

Faster two-dimensional pattern matching with $k$ mismatches

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ellert, Jonas, Gawrychowski, Paweł, Górkiewicz, Adam, Starikovskaya, Tatiana
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

Better Indexing for Rectangular Pattern Matching
by: Gawrychowski, Paweł, et al.
Published: (2025)

Small Space Encoding and Recognition of $k$-Palindromic Prefixes
by: Bathie, Gabriel, et al.
Published: (2024)

Faster ED-String Matching with $k$ Mismatches
by: Gawrychowski, Paweł, et al.
Published: (2025)

Equivalences between Non-trivial Variants of 3LDT and Conv3LDT
by: Dudek, Bartłomiej, et al.
Published: (2020)

Balancing Two-Dimensional Straight-Line Programs
by: Boneh, Itai, et al.
Published: (2025)

Streaming periodicity with mismatches, wildcards, and edits
by: Ghazi, Taha El, et al.
Published: (2025)

Longest Common Extensions with Wildcards: Trade-off and Applications
by: Bathie, Gabriel, et al.
Published: (2024)

Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
by: Gawrychowski, Paweł, et al.
Published: (2024)

On Incremental Approximate Shortest Paths in Directed Graphs
by: Górkiewicz, Adam, et al.
Published: (2025)

Optimal Distance Labeling for Permutation Graphs
by: Gawrychowski, Paweł, et al.
Published: (2024)

Enumerating All Directed Spanning Trees in Optimal Time
by: Gawrychowski, Paweł, et al.
Published: (2026)

Time-Optimal Construction of String Synchronizing Sets
by: Ellert, Jonas, et al.
Published: (2026)

Core-Sparse Monge Matrix Multiplication: Improved Algorithm and Applications
by: Gawrychowski, Paweł, et al.
Published: (2024)

Enumerating m-Length Walks in Directed Graphs with Constant Delay
by: Adamson, Duncan, et al.
Published: (2024)

Dynamic Longest Common Substring in Polylogarithmic Time
by: Charalampopoulos, Panagiotis, et al.
Published: (2020)

Pattern Matching with Mismatches and Wildcards
by: Bathie, Gabriel, et al.
Published: (2024)

Internal Pattern Matching in Small Space and Applications
by: Bathie, Gabriel, et al.
Published: (2024)

Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
by: Bathie, Gabriel, et al.
Published: (2023)

Approximate Cartesian Tree Matching with Substitutions
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

Optimal Bounds for Distinct Quartics
by: Charalampopoulos, Panagiotis, et al.
Published: (2024)

Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration
by: Gawrychowski, Pawel, et al.
Published: (2024)

Faster Combinatorial k-Clique Algorithms
by: Abboud, Amir, et al.
Published: (2024)

Faster algorithms for k-Orthogonal Vectors in low dimension
by: Dürr, Anita, et al.
Published: (2025)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
by: Kadria, Avi, et al.
Published: (2025)

Faster Approximation Algorithms for k-Center via Data Reduction
by: Filtser, Arnold, et al.
Published: (2025)

A Faster Algorithm for Constrained Correlation Clustering
by: Fischer, Nick, et al.
Published: (2025)

Faster exact learning of k-term DNFs with membership and equivalence queries
by: Alman, Josh, et al.
Published: (2025)

3SUM in Preprocessed Universes: Faster and Simpler
by: Kasliwal, Shashwat, et al.
Published: (2024)

A Faster $k$-means++ Algorithm
by: Liang, Jiehao, et al.
Published: (2022)

Faster and Simpler Greedy Algorithm for $k$-Median and $k$-Means
by: la Tour, Max Dupré, et al.
Published: (2024)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
by: Ashvinkumar, Vikrant, et al.
Published: (2024)

Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than $3^k$
by: Liu, Yuxi, et al.
Published: (2024)

Approximating the shortest path problem with scenarios
by: Kasperski, Adam, et al.
Published: (2018)

Optimal-Length Labeling Schemes and Fast Algorithms for k-gathering and k-broadcasting
by: Ganczorz, Adam, et al.
Published: (2025)

Faster Approximation Scheme for Euclidean $k$-TSP
by: van Wijland, Ernest, et al.
Published: (2023)

Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing
by: Bringmann, Karl, et al.
Published: (2024)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
by: Nogler, Jakob, et al.
Published: (2024)

Recoverable robust shortest path problem under interval budgeted uncertainty representations
by: Jackiewicz, Marcel, et al.
Published: (2024)

Optimizations and extensions for fair join pattern matching
by: Karras, Ioannis
Published: (2025)