  Suffix trees and suffix arrays are two of the most widely used data
structures for text indexing. Each uses linear space and can be constructed in
linear time for polynomially sized alphabets. However, when it comes to
answering queries with worst-case deterministic time bounds, the prior does so
in $O(m\log|\Sigma|)$ time, where $m$ is the query size, $|\Sigma|$ is the
alphabet size, and the latter does so in $O(m+\log n)$ time, where $n$ is the
text size. If one wants to output all appearances of the query, an additive
cost of $O(occ)$ time is sufficient, where $occ$ is the size of the output.
  We propose a novel way of combining the two into, what we call, a {\em suffix
tray}. The space and construction time remain linear and the query time
improves to $O(m+\log|\Sigma|)$ for integer alphabets from a linear range, i.e.
$\Sigma \subset \{1,\cdots, cn\}$, for an arbitrary constant $c$. The
construction and query are deterministic. Here also an additive $O(occ)$ time
is sufficient if one desires to output all appearances of the query.
  We also consider the online version of indexing, where the text arrives
online, one character at a time, and indexing queries are answered in tandem.
In this variant we create a cross between a suffix tree and a suffix list (a
dynamic variant of suffix array) to be called a {\em suffix trist}; it supports
queries in $O(m+\log|\Sigma|)$ time. The suffix trist also uses linear space.
Furthermore, if there exists an online construction for a linear-space suffix
tree such that the cost of adding a character is worst-case deterministic
$f(n,|\Sigma|)$ ($n$ is the size of the current text), then one can further
update the suffix trist in $O(f(n,|\Sigma|)+\log |\Sigma|)$ time. The best
currently known worst-case deterministic bound for $f(n,|\Sigma|)$ is $O(\log
n)$ time.

Data Structures and Algorithms