SORTING SUFFIXES OF TWO-PATTERN STRINGS

Recently, several authors presented linear recursive algorithms for sorting suffixes of a string. All these algorithms employ a similar three-step approach, based on an initial division of the suffixes of x into two sets: Step 1 sorts the first set using recursive reduction of the problem, Step 2 determines the order of the suffixes in the second set based on the order of the suffixes in the first set, and Step 3 merges the two sets together. …