A Textbook Solution for Dynamic Strings
Zsuzsanna Lipták, Francesco Masillo, and Gonzalo Navarro
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 O(log N) whp for the updates
and O(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 O(log n) amortized time,
n being the sum of the lengths of the strings involved in the operation.
The length l of the longest common prefix is computed in O(log n +
log^2 l) amortized time. Our query results are correct whp. Our simpler
solution enables other more general updates in O(log n) amortized time,
such as reversing a substring and/or mapping its symbols. We can also make
FeST use compact space, and extend it to regard substrings as circular or as their omega extension.