A fully-dynamic data structure for external substring search
Paolo Ferragina, Roberto Grossi · 1995
We address the issue of efficiently searching on external dynamic data structures for strings, introducing the External Dynamic Substring Search problem.Consider a set A of (external) text strings kept into secondary storage.The set A can be dynamically changed by inserting or deleting strings, and on-line searched to find all the occurrences of an arbitrary pattern string as a substringof the text strings in A.We introduce the SB-Tree data structure for A, which is the first fully-dynamic data structure allowing the External Dynamic Substring Search problem to be solved with provably good worst-case and amortized 1/0 bounds.It requires optimal space and makes the on-line search alphabet independent also into main memory.The SB-tree can also be used to solve a natural extension of our problem to parameterized strings (p-strings) within the same bounds.