advanced data structures and implementation array of length three and thus have fourfourand three suffixesrespectively ' suffixes are [abr][aca][dab][ra$][aca][dab][ra$][dab][ra$][ra$]which clearly correspond to the suffixes abracadabraacadabradabraand ra in the original string in the original string sthese suffixes are located at indices and respectivelyso looking at all three of and we can see that each si represents the suffixes that are located at indices mod in step concatenate and and recursively compute the suffix array in order to compute this suffix arraywe will need to sort the new alphabet of tri-characters this can be done in linear time by three passes of radix sortsince the old characters were already sorted in step if in fact all the tri-characters in the new alphabet are uniquethen we do not even need to bother with recursive call making three passes of radix sort takes linear time if (nis the running time of the suffix array construction algorithmthen the recursive call takes ( / time examplein our example [bra][cad][abr][ $$][rac][ada][brathe sorted suffixes that will be computed recursively will represent tri-character strings as shown in figure notice that these are not exactly the same as the corresponding suffixes in showeverif we strip out characters starting at the first $we do have match of suffixes also note that the indices returned by the recursive call do not correspond directly to the indices in sthough it is simple matter to map them back so to see how the algorithm actually forms the recursive callobserve that three passes of radix sort will assign the following alphabet[ $$ [abr [ada [bra [cad [rac figure shows the mapping of tri-charactersthe resulting array that is formed for and the resulting suffix array that is computed recursively index substring being represented [ $$[rac[ada[bra [abr[ $$[rac[ada[bra [ada[bra [bra [bra[cad[abr[ $$[rac[ada[bra [cad[abr[ $$[rac[ada[bra [rac[ada[brafigure suffix array for in tri-character set