advanced data structures and implementation since this is standard mergewith at most two comparisons per suffix pairthis step takes linear time the entire algorithm thus satisfies (nt( / on and takes linear time although we have only computed the suffix arraythe lcp information can also be computed as the algorithm runsbut there are some tricky details that are involvedand often the lcp information is computed by separate linear-time algorithm we close by providing working implementation to compute suffix arraysrather than fully implementing step to sort the original characterswe'll assume only small set of ascii characters (residing in values - are present in the string in figure we allocate the arrays that have three extra slots for padding and call makesuffixarraywhich is the basic linear-time algorithm figure shows makesuffixarray at lines to it allocates all the needed arrays and makes sure that and have the same number of elements (lines to )it then delegates work to assignnamescomputesl computes and merge /find the suffix array sa of [ - in { kn /requires [ ]= [ + ]= [ + ]= >= void makesuffixarrayconst vector svector saint nint int int int int / iff % = int tvector )vector sa )vector )vector sa )/generate positions in for items in /the "+tadds dummy mod suffix if % = /at that pointthe size of is forint ++ ifi ! +iint assignnamesss sa )computes sa )computes ss sa sa )mergess sasa sa nn )figure the main routine for linear-time suffix array construction