Now to the full algorithm for building the suffix array, finally. So procedure BuildSuffixArray takes in only string S and returns the order of the cyclic shifts or of the suffixes of this string. We assume that S already has $ in the and, and $ is smaller than all the characters in the string. We start with sorting the characters, single character cyclic shifts of S, and save the result in the right order. And also compute the equivalence classes of those characters and save the result in the right class. And we initialize the current length as one. And then we have the main loop, which proceeds while the current length is still less, strictly less than the length of the string. If it is, then we first need to sort the double cyclic shifts of length to L. And then we also need to update their equivalence classes so that the next iteration can use them to again sort the doubled cyclic shifts. And then we just multiply L by 2, and go on in our while loop until we get to the station when L is more than or equal to the length of S. And by the time array order will contain the correct order of all the full cyclic shifts of the string S, which is the same as the correct order of all the suffixes of the string S if it has a $ on the end. And the running time of BuildSuffixArray procedure is length of S times logarithm of that, plus size of the alphabet. So the size of the alphabet is because of the counting sort of characters in the beginning. because we're sorted them in time proportional to length of the string plus size of the alphabet. But if we wanted, we could just sort them in time S log S without using the count and sort to sort the characters. So we could actually remove the plus alphabet from the BuildSuffixArray asymptotics. Although in practice usually the alphabet is very small, so we don't need to do that. And using counting sorts is better than actually sorting the characters in S log S. And also compute the classes of the characters in linear time after that. In each while loop iteration, we do both sorting of the double cyclic shifts and update their clusters in linear time. And we have only logarithmic number of iterations, because L is doubled every iteration, and as soon as it gets at least S or more, we stop. So it's on a logarithmic number of iterations, so all in all, the while loop runs for S log S. And adding to that, the initialization cost, we get S log S plus size of the alphabet. So now you finally can build suffix array of a string S in time length of S times logarithm of that using linear mode mode of memory. And you can do not only that, but you can also sort all cyclic shifts of a string in the same time. And you know that suffix array handles many fast operations with the string. And also, in the next lesson you will learn to build suffix tree of the string from its suffix array in linear time. And that combined will give you an algorithm to build suffix tree in time S log S. And of course you already knew how to build a suffix tree in quadratic time, but S log S is much, much better than that. So you will learn that in the next lesson.
