Buchumschlag

Longest Common Extensions with Wildcards: Trade-off and Applications

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bathie, Gabriel, Boneh, Itai, Charalampopoulos, Panagiotis, Ellert, Jonas, Starikovskaya, Tatiana
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Pattern Matching with Mismatches and Wildcards
von: Bathie, Gabriel, et al.
Veröffentlicht: (2024)

Internal Pattern Matching in Small Space and Applications
von: Bathie, Gabriel, et al.
Veröffentlicht: (2024)

Small Space Encoding and Recognition of $k$-Palindromic Prefixes
von: Bathie, Gabriel, et al.
Veröffentlicht: (2024)

Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2026)

Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares
von: Bathie, Gabriel, et al.
Veröffentlicht: (2023)

Approximate Cartesian Tree Matching with Substitutions
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2026)

Dynamic Longest Common Substring in Polylogarithmic Time
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2020)

Faster Algorithms for Longest Common Substring
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2021)

Faster two-dimensional pattern matching with $k$ mismatches
von: Ellert, Jonas, et al.
Veröffentlicht: (2024)

Deterministic Longest Common Subsequence Approximation in Near-Linear Time
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Longest Common Extension of a Dynamic String in Parallel Constant Time
von: Albert, Daniel
Veröffentlicht: (2026)

Time-Optimal Construction of String Synchronizing Sets
von: Ellert, Jonas, et al.
Veröffentlicht: (2026)

Streaming periodicity with mismatches, wildcards, and edits
von: Ghazi, Taha El, et al.
Veröffentlicht: (2025)

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
von: Bathie, Gabriel, et al.
Veröffentlicht: (2025)

Equivalences between Non-trivial Variants of 3LDT and Conv3LDT
von: Dudek, Bartłomiej, et al.
Veröffentlicht: (2020)

Dynamic Pattern Matching with Wildcards
von: Naeini, Arshia Ataee, et al.
Veröffentlicht: (2026)

Quantum Pattern Matching with Wildcards
von: Seddighin, Masoud, et al.
Veröffentlicht: (2025)

Hamming Distance Oracle
von: Boneh, Itai, et al.
Veröffentlicht: (2024)

Balancing Two-Dimensional Straight-Line Programs
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

Pattern Matching under Weighted Edit Distance
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2025)

An Algorithm for the Longest Common Subsequence and Substring Problem for Multiple Strings
von: Li, Rao
Veröffentlicht: (2024)

Improved Lower Bounds on the Expected Length of Longest Common Subsequences
von: Heineman, George T., et al.
Veröffentlicht: (2024)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
von: Boneh, Itai, et al.
Veröffentlicht: (2025)

On Time-Memory Tradeoffs for Maximal Palindromes with Wildcards and $k$-Mismatches
von: Amir, Amihood, et al.
Veröffentlicht: (2026)

Optimal Bounds for Distinct Quartics
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2024)

The Longest Common Bitonic Subsequence: A Match-Sensitive Dynamic Programming Approach
von: Rahat, Md. Tanzeem, et al.
Veröffentlicht: (2025)

Searching 2D-Strings for Matching Frames
von: Boneh, Itai, et al.
Veröffentlicht: (2023)

The Trichotomy of Regular Property Testing
von: Bathie, Gabriel, et al.
Veröffentlicht: (2025)

Subtree Mode and Applications
von: Zhou, Jialong, et al.
Veröffentlicht: (2025)

Faster Algorithms for Shortest Unique or Absent Substrings
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2026)

Counting Distinct Square Substrings in Sublinear Time
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2025)

Range Longest Increasing Subsequence and its Relatives
von: S., Karthik C., et al.
Veröffentlicht: (2024)

String 2-Covers with No Length Restrictions
von: Boneh, Itai, et al.
Veröffentlicht: (2024)

Analyzing and Leveraging the $k$-Sensitivity of LZ77
von: Bathie, Gabriel, et al.
Veröffentlicht: (2026)

Approximate Circular Pattern Matching under Edit Distance
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2024)

Subsequence Covers of Words
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2025)

Longest Unbordered Factors on Run-Length Encoded Strings
von: Sekizaki, Shoma, et al.
Veröffentlicht: (2025)

Approximate Circular Pattern Matching
von: Charalampopoulos, Panagiotis, et al.
Veröffentlicht: (2022)