|
We deal with the problem of maintaining
the suffix tree indexing structure
for a fully-online collection of strings,
where a new character can be prepended
to any string in the collection at any time.
The only previously known algorithm for the problem,
recently proposed by Takagi et al. [Algorithmica 82(5): 1346-1377 (2020)],
runs in O(N log σ) time and O(N) space on the word RAM model,
where N denotes the total length of the strings
and σ denotes the alphabet size.
Their algorithm makes heavy use of the nearest marked ancestor (NMA)
data structure on semi-dynamic trees,
that can answer queries and supports insertion of nodes
in O(1) amortized time on the word RAM model.
In this paper, we present a simpler fully-online right-to-left
algorithm that builds the suffix tree for a given string collection
in O(N (log σ + log d)) time and O(N) space,
where d is the maximum number of in-coming Weiner links to a node
of the suffix tree.
We note that d is bounded by the height of the suffix tree,
which is further bounded by the length of the longest string in the collection.
The advantage of this new algorithm is that it works on
the pointer machine model, namely, it does not use the complicated
NMA data structures that involve table look-ups.
As a byproduct, we also obtain a pointer-machine algorithm
for building the directed acyclic word graph (DAWG)
for a fully-online left-to-right collection of strings,
which runs in O(N (log σ + log d)) time and O(N) space
again without the aid of the NMA data structures.
|
