Dynamic string searching
Arne Andersson, Mikkel Thorup · Symposium on Discrete Algorithms · 2001
Optimal bounds are presented for dynamic string searching. If the longest common prefix between a query key x and a currently stored string y is e words, then finding the stored string lexicographically nearest to x takes optimal T(√log n/log log n + e) time. Similarly, we can insert and delete strings from the stored set within this time bound. The space requirements is linear and the time bounds are worst-case.