A textbook solution for dynamic strings

DOI10.1016/J.TCS.2026.115746MaRDI QIDQ6858872zbMATH OpenFDO

Authors Zsuzsanna Lipták, Francesco Masillo, Gonzalo Navarro

Publication date 12 February 2026

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2026.115746

zbMATH Keywords

binary search treesdynamic data structuresdynamic stringssplay trees

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Cites work

• r-indexing the eBWT
• A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors
• Algorithmic Number Theory
• An extension of the Burrows-Wheeler transform
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Approximate circular pattern matching
• Approximating edit distance in the fully dynamic model
• Combinatorics of genome rearrangements.
• Computing the original eBWT faster, simpler, and with less memory
• Dynamic and internal longest common substring
• Dynamic index and LZ factorization in compressed space
• Dynamic String Alignment.
• Dynamic suffix array with polylogarithmic queries and updates
• Efficient randomized pattern-matching algorithms
• Finding the cyclic covers of a string
• Fully dynamic data structure for LCE queries in compressed space
• Fully functional static and dynamic succinct trees
• scientific article; zbMATH DE number 1263193 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 6850408 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 1445383 (Why is no real title available?)
• scientific article; zbMATH DE number 7740911 (Why is no real title available?)
• Improved approximation for breakpoint graph decomposition and sorting by reversals
• Linear-time computation of cyclic roots and cyclic covers of a string
• Longest common factor after one edit operation
• Longest Lyndon Substring After Edit
• Longest substring palindrome after edit
• Maintaining dynamic sequences under equality tests in polylogarithmic time
• Modular subset sum, dynamic strings, and zero-sum sets
• On the Dynamic Finger Conjecture for Splay Trees. Part II: The Proof
• Pattern Matching in Lempel-Ziv Compressed Strings: Fast, Simple, and Deterministic
• Permutation patterns in genome rearrangement problems: the reversal model
• Repetition Detection in a Dynamic String
• Self-adjusting binary search trees
• The Smallest Grammar Problem
• Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences
• Universal compressed text indexing
• Upper and lower bounds for dynamic data structures on strings

This page was built for publication: A textbook solution for dynamic strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6858872)