Cover Image

Fast Computation of $k$-Runs, Parameterized Squares, and Other Generalised Squares

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Nakashima, Yuto, Radoszewski, Jakub, Waleń, Tomasz
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Counting Distinct Square Substrings in Sublinear Time
by: Charalampopoulos, Panagiotis, et al.
Published: (2025)

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

On the Number of Non-equivalent Parameterized Squares in a String
by: Hamai, Rikuya, et al.
Published: (2024)

Subsequence Covers of Words
by: Charalampopoulos, Panagiotis, et al.
Published: (2025)

Approximate Circular Pattern Matching under Edit Distance
by: Charalampopoulos, Panagiotis, et al.
Published: (2024)

Approximate Circular Pattern Matching
by: Charalampopoulos, Panagiotis, et al.
Published: (2022)

Computing String Covers in Sublinear Time
by: Radoszewski, Jakub, et al.
Published: (2024)

Faster Algorithms for Longest Common Substring
by: Charalampopoulos, Panagiotis, et al.
Published: (2021)

Structural Parameterizations of $k$-Planarity
by: Gima, Tatsuya, et al.
Published: (2025)

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

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

Faster Space-Efficient STR-IC-LCS Computation
by: Yonemoto, Yuki, et al.
Published: (2022)

Fast Computation of the Discrete Fourier Transform Square Index Coefficients
by: Queiroz, Saulo, et al.
Published: (2024)

Parameterized algorithms for $k$-Inversion
by: Antony, Dhanyamol, et al.
Published: (2026)

Tight bounds for the sensitivity of CDAWGs with left-end edits
by: Fujimaru, Hiroto, et al.
Published: (2023)

Computing maximal palindromes in non-standard matching models
by: Mieno, Takuya, et al.
Published: (2022)

SquareSort: a cache-oblivious sorting algorithm
by: Koucký, Michal, et al.
Published: (2024)

Pattern Masking for Dictionary Matching
by: Charalampopoulos, Panagiotis, et al.
Published: (2020)

LZBE: an LZ-style compressor supporting $O(\log n)$-time random access
by: Shibata, Hiroki, et al.
Published: (2025)

Elastic-Degenerate String Comparison
by: Gabory, Esteban, et al.
Published: (2024)

Approximation Algorithms for Clustering with Minimum Sum of Radii, Diameters, and Squared Radii
by: Friggstad, Zachary, et al.
Published: (2024)

Sum-Of-Squares To Approximate Knapsack
by: Kothari, Pravesh K., et al.
Published: (2025)

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

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
by: Fujie, Yuto, et al.
Published: (2025)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
by: Kothari, Pravesh, et al.
Published: (2024)

Parameterized Algorithms for Computing Pareto Sets
by: Könen, Joshua, et al.
Published: (2025)

Parameterized Algorithms for Computing MAD Trees
by: Breitkopf, Tom-Lukas, et al.
Published: (2026)

Sensitivity of Repetitiveness Measures to String Reversal
by: Bannai, Hideo, et al.
Published: (2026)

Edit and Alphabet-Ordering Sensitivity of Lex-parse
by: Nakashima, Yuto, et al.
Published: (2024)

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
by: Brand, Jan van den, et al.
Published: (2025)

On the compressiveness of the Burrows-Wheeler transform
by: Bannai, Hideo, et al.
Published: (2024)

On Approximating the Weighted Region Problem in Square Tessellations
by: Kakimura, Naonori, et al.
Published: (2024)

Counting distinct (non-)crossing substrings
by: Umezaki, Haruki, et al.
Published: (2025)

Subsequence Matching and LCS under Cartesian-Tree Equivalence
by: Tsujimoto, Taketo, et al.
Published: (2024)

Fully Polynomial-time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication
by: Bentert, Matthias, et al.
Published: (2024)

Revisiting Approximate Leverage Score Sketching for Matrix Least Squares
by: Larsen, Brett W., et al.
Published: (2022)

Computing k-mers in Graphs
by: Alanko, Jarno N., et al.
Published: (2025)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

Fast $k$-means Seeding Under The Manifold Hypothesis
by: Shah, Poojan, et al.
Published: (2026)

An Efficient Frequency-Based Approach for Maximal Square Detection in Binary Matrices
by: Bhandari, Swastik
Published: (2025)