A bidirectional reduction between suffix random access and function inversion enables improved asymmetric streaming algorithms for exact/approximate pattern matching and relative Lempel-Ziv compression.
Starikovskaya, and Hjalte Wedel Vildhøj
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
fields
cs.DS 2roles
background 1polarities
background 1representative citing papers
Dynamic LCS maintained under edits in amortized O(log^7 n) time whp, with Omega(log n / log log n) lower bound.
citing papers explorer
-
Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
A bidirectional reduction between suffix random access and function inversion enables improved asymmetric streaming algorithms for exact/approximate pattern matching and relative Lempel-Ziv compression.
-
Dynamic Longest Common Substring in Polylogarithmic Time
Dynamic LCS maintained under edits in amortized O(log^7 n) time whp, with Omega(log n / log log n) lower bound.