Cover Image

Small Space Encoding and Recognition of $k$-Palindromic Prefixes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bathie, Gabriel, Ellert, Jonas, 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

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

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

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

Faster two-dimensional pattern matching with $k$ mismatches
by: Ellert, Jonas, et al.
Published: (2024)

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

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

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

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

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
by: Bathie, Gabriel, et al.
Published: (2025)

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

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

Analyzing and Leveraging the $k$-Sensitivity of LZ77
by: Bathie, Gabriel, et al.
Published: (2026)

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

Combinatorics of Palindromes
by: Itzhaki, Michael
Published: (2025)

The Trichotomy of Regular Property Testing
by: Bathie, Gabriel, et al.
Published: (2025)

Asymptotically Optimal Representation of Palindromic Structure
by: Itzhaki, Michael
Published: (2024)

Maximal Palindromes in MPC: Simple and Optimal
by: Pissis, Solon P.
Published: (2025)

Online Computation of Palindromes and Suffix Trees on Tries
by: Shibata, Hiroki, et al.
Published: (2026)

Explicit Combinatoric Structures of Palindromes and Chromatic Number of Restriction Graphs
by: Amir, Amihood, et al.
Published: (2024)

Prefix-free parsing for merging big BWTs
by: Diaz-Dominguez, Diego, et al.
Published: (2025)

Revisit the Partial Coloring Method: Prefix Spencer and Sampling
by: Cai, Dongrun, et al.
Published: (2024)

LLM Query Scheduling with Prefix Reuse and Latency Constraints
by: Dexter, Gregory, et al.
Published: (2025)

All-Pairs Suffix-Prefix on Fully Dynamic Set of Strings
by: Kikuchi, Masaru, et al.
Published: (2024)

Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings
by: Hammer, Nina, et al.
Published: (2022)

Bubble-Flip -- A New Generation Algorithm for Prefix Normal Words
by: Cicalese, Ferdinando, et al.
Published: (2017)

Space-Efficient k-Mismatch Text Indexes
by: Kociumaka, Tomasz, et al.
Published: (2025)

Depth first representations of $k^2$-trees
by: Carmona, Gabriel, et al.
Published: (2025)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
by: Bhattacharya, Sayan, et al.
Published: (2024)

Space-Efficient Depth-First Search via Augmented Succinct Graph Encodings
by: Elberfeld, Michael, et al.
Published: (2025)

A Sierpinski Triangle Data Structure for Efficient Array Value Update and Prefix Sum Calculation
by: Harrison, Brent, et al.
Published: (2024)

Fast Iteration of Spaced k-mers
by: Czech, Lucas
Published: (2026)

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
by: Kempa, Dominik, et al.
Published: (2025)

Prefix Sums via Kronecker Products
by: Sobczyk, Aleksandros, et al.
Published: (2025)

Double-Ended Palindromic Trees in Linear Time
by: Wang, Qisheng, et al.
Published: (2022)

The General Expiration Streaming Model: Diameter, $k$-Center, Counting, Sampling, and Friends
by: Blank, Lotte, et al.
Published: (2025)

On $k$-connectivity oracles in $k$-connected graphs
by: Nutov, Zeev
Published: (2026)

Succinct Planar Encoding with Minor Operations
by: Kammer, Frank, et al.
Published: (2023)

Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language
by: Khadiev, Kamil, et al.
Published: (2024)

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

Compressed Dictionary Matching on Run-Length Encoded Strings
by: Bille, Philip, et al.
Published: (2025)