# More Time-Space Tradeoffs for Finding a Shortest Unique Substring
## 4 A Deterministic Algorithm
### Finding Occurrences of Suffixes of \(X\)  
To enumerate all occurrences of suffixes of \(x\) in \(T\), we construct the Directed Acyclic Word Graph (DAWG) [16]\(D(x\$)\) with suffix links. \(D(x\$)\) is the smallest deterministic automaton which accepts all suffixes of \(x\$\) and it is known to have the following properties:  
1. Each edge is labeled by a single symbol, and the labels of all outgoing edges from a given node are distinct. The total number of nodes and edges is linear in the length of \(x\$\).
2. For any node \(u\), let \(P_{u}\) denote the set of strings that can be created by concatenating the labels of any path from the root to \(u\). Subsequently, \(P_{u}\subseteq Substr(x\$)\), and for any strings \(p_{1},p_{2}\in P_{u}\), the set of ending positions of occurrences of \(p_{1}\) and \(p_{2}\) in \(x\$\) are equivalent, i.e., \[\{j\mid p_{1}=\hat{x}[j-|p_{1}|+1..j]\}=\{j\mid p_{2}=\hat{x}[j-|p_{2}|+1..j]\}\] where \(\hat{x}=x\$\). This implies that \(P_{u}=\{p_{u}[1..|p_{u}|],\ldots,p_{u}[k..|p_{u}|]\}\) for some \(p_{u}\) (the longest element of \(P_{u}\)) and \(1\leq k\leq|p_{u}|\).
3. The suffix link \(l(u)\) of a node \(u\) points to a node \(v\) such that the longest element of \(P_{v}\) is \(p_{u}^{\prime}[2..|p_{u}^{\prime}|]\), where \(p_{u}^{\prime}\) is the shortest element of \(P_{u}\).  
For technical convenience, we can also consider an auxiliary node that the suffix link of the root points to, which has outgoing edges for all symbols to the root. \(D(x\$)\) can be built in \(\mathcal{O}(m\log\sigma)\) time and \(\mathcal{O}(m)\) space [16]. Because the suffix links form a tree, we can also process the suffix link tree in linear time so that each node \(u\) holds a pointer \(l^{\prime}(u)\) to the deepest ancestor \(v\) of \(u\) (possibly \(v=u\)) that has \(\$\) as an outgoing edge, i.e., the longest element \(p_{v}\) of \(P_{v}\) is the longest suffix of any \(p\in P_{u}\) that is a suffix of \(x\).  
Using \(D(x\$)\), we can incrementally compute for each \(j=1,\ldots,n\), the position in the DAWG, which corresponds to the longest suffix \(T[i..j]\) of \(T[1..j]\) that is a substring of \(x\) in \(O(n\log\sigma)\) overall time. Initially, \(i=1\), and we start at the root of \(D(x\$)\). For each character \(T[j]\) for \(j=1,\ldots,n\) and current node \(u\), we traverse \(D(x\$)\) by following the edge labelled \(T[j]\) from \(u\) or if that edge does not exist, try again after following the suffix link to \(l(u)\). When the suffix link is traversed, \(i\) is incremented, so that the length of \(T[i..j-1]\) matches the length of the longest element in \(P_{l(u)}\) (\(-1\) for the auxiliary node, and \(0\) for the root node).  
If, upon reading character \(T[j^{*}]\), we arrive at a node \(u\), then, \(v=l^{\prime}(u)\) points to the (possibly empty) longest suffix \(T[i^{*}..j^{*}]\) of \(T[1..j^{*}]\) that is a suffix of \(x\), so we have detected suffixes of \(x\) with lengths \(0..j^{*}-i^{*}+1\) starting at positions \(i\in[i^{*},j^{*}]\) and ending at position \(j^{*}\) of \(T\). In this manner, we can find occurrences of all suffixes of \(x\) in \(T\) in \(\mathcal{O}(n\log\sigma)\) time.