## 4 Algorithm II: Improved Algorithm
### Improved Sorting - Using Shannon-Fano-Elias Codes
This can be performed in linear time using counting sort. Since \(|\Sigma|\leq n\), this gives a worst case time bound of \(O(n)\) to compute the required codes for all the \(O(n)\)\(m\)-length blocks. \(\square\)  
Figure 5(b) shows a continuation of the previous example, with the old \(m\)-block: \(Q_{i}=acabd\), and a new \(m\)-block \(Q_{i+1}=cabda\). That is, the new symbol \(a\) has been shifted in, while the first symbol in the old block has been shifted out. We observe that the general structure in Figure 5(a) is not changed by the incoming symbol, except only at the first step and last step. For the running example, the new value will be \(q_{i+1}=\frac{1051}{2048}\). Table 2 shows the evolution of the upper and lower bounds for the two adjacent \(m\)-blocks. The bounds are obtained from the figures. Having determined \(q_{i}\), which is fractional, we can then assign the final code for \(Q_{i}\) by mapping the tags to an integer in the range \([0\ \ n-1]\). This can be done using a simple formula:  
\[P_{i}=\frac{P_{i}^{\prime}}{\sum_{i=0}^{n-1}P_{i}^{\prime}} \tag{1}\]3  
where \(q_{min}=\min_{i}\{q_{i}\}\), and \(q_{max}=\max_{i}\{q_{i}\}\). Notice that here, the \(c_{i}\)'s computed will not necessarily be consecutive. But they will be ordered. Also, the number of distinct \(q_{i}\)'s is at most \(n\). The difference between \(c_{i}\) and \(c_{i+1}\) will depend on \(P_{i}\) and \(P_{i+1}\). The floor function, however, could break down the lexicographic ordering. A better approach is to simply record the position where each \(Q_{i}\) fell on the number line. We then read off these positions from 0 to 1, and use the count at which each \(Q_{i}\) is encountered as its code. This is easily done using the cummulative count of occurence of each distinct \(Q_{i}\). Since the \(q_{i}\)'s are implicitly sorted, so are the \(c_{i}\)'s. We have thus obtained an ordering of all the \(m\)-length substrings in \(T\). This is still essentially a **partial ordering** of all the suffixes based on their first \(m\) symbols, but a total order on the distinct \(m\)-length prefixes of the suffixes. \begin{table}
\begin{tabular}{c|c c c c c||c c c c} \hline  & \(a\) & \(c\) & \(a\) & \(b\) & \(d\) & \(c\) & \(a\) & \(b\) & \(d\) & \(a\) \\ \hline \(U_{k}\) & \(1\) & \(\frac{1}{4}\) & \(\frac{3}{16}\) & \(\frac{9}{64}\) & \(\frac{17}{128}\) & \(1\) & \(\frac{3}{4}\) & \(\frac{9}{16}\) & \(\frac{17}{32}\) & \(\frac{17}{32}\) \\ \(L_{k}\) & \(0\) & \(0\) & \(\frac{1}{8}\) & \(\frac{1}{8}\) & \(\frac{33}{256}\) & \(0\) & \(\frac{1}{2}\) & \(\frac{1}{2}\) & \(\frac{33}{64}\) & \(\frac{135}{256}\) \\ \(U_{k}-L_{k}\) & \(1\) & \(\frac{1}{4}\) & \(\frac{1}{16}\) & \(\frac{1}{64}\) & \(\frac{1}{256}\) & \(1\) & \(\frac{1}{4}\) & \(\frac{1}{16}\) & \(\frac{1}{64}\) & \(\frac{1}{256}\) \\ \hline \end{tabular}
\end{table} 
Table 2: Upper and lower bounds on the current interval on the number line. We now present our main results in the following theorems:  
**Theorem 2:** Given the sequence \(T=t_{0}t_{1}\ldots t_{n-1}\), from a fixed alphabet \(\Sigma\), \(|\Sigma|\leq n\), all the \(m\)-length prefixes of the suffixes of \(T\) can be ordered in linear time and linear space in the worst case. _Proof._ The theorem follows from Lemmas 2 to 4. The correctness of the ordering follows from Lemma 2 and Lemma 3. The time complexity follows from Lemma 3. What remains is to prove is the space complexity. We only need to maintain two extra \(O(|\Sigma|)\) arrays, one for the number line at each step, and the other to keep the cumulative distribution function. Thus, the space needed is also linear in \(O(n+m+|\Sigma|)=O(n)\). \(\square\)  
**Theorem 3:** Given the sequence \(T=t_{0}t_{1}\ldots t_{n-1}\), with symbols from a fixed alphabet \(\Sigma\), \(|\Sigma|\leq n\), Algorithm II computes the suffix array of \(T\) in \(O(n)\) worst case time and space. _Proof._ At each iteration, the recursive call applies only to the \(\frac{2}{3}n\) suffixes in \(T_{2}\).