A Textbook Solution for Dynamic Strings
arxiv(2024)
摘要
We consider the problem of maintaining a collection of strings while
efficiently supporting splits and concatenations on them, as well as comparing
two substrings, and computing the longest common prefix between two suffixes.
This problem can be solved in optimal time 𝒪(log N) whp for the
updates and 𝒪(1) worst-case time for the queries, where N is the
total collection size [Gawrychowski et al., SODA 2018]. We present here a much
simpler solution based on a forest of enhanced splay trees (FeST), where both
the updates and the substring comparison take 𝒪(log n) amortized
time, n being the lengths of the strings involved. The longest common prefix
of length ℓ is computed in 𝒪(log n + log^2ℓ) amortized
time. Our query results are correct whp. Our simpler solution enables other
more general updates in 𝒪(log n) amortized time, such as reversing
a substring and/or mapping its symbols. We can also regard substrings as
circular or as their omega extension.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要