step sort the characters in the stringassigning them numbers sequentially starting at then use those numbers for the remainder of the algorithm note that the numbers that are assigned depend on the text soif the text contains dna characters acgand onlythen there will be only four numbers then pad the array with three to avoid boundary cases if we assume that the alphabet is fixed sizethen the sort takes some constant amount of time examplein our examplethe mapping is and the transformation can be visualized in figure step divide the text into three groupss [ ] [ ] [ for the idea is that each of consists of roughly / symbolsbut the symbols are no longer the original alphabetbut instead each new symbol is some group of three symbols from the original alphabet we will call these tri-characters most importantlythe suffixes of and combine to form the suffixes of thus one idea would be to recursively compute the suffixes of and (which by definition implicitly represent sorted stringsand then merge the results in linear time howeversince this would be three recursive calls on problems / the original sizethat would result in an on log algorithm so the idea is going to be to avoid one of the three recursive callsby computing two of the suffix groups recursively and using that information to compute the third suffix group examplein our exampleif we look at the original character set and use to represent the padded characterwe get [abr][aca][dab][ra$ [bra][cad][abr][ $$ [rac][ada][brawe can see that in and each tri-character is now trio of characters from the original alphabet using that alphabets and are arrays of length four and is an input strings new problem index figure mapping of character in string to an array of integers