Suffix array: Difference between revisions

Revision as of 23:11, 29 January 2007

Revision as of 20:54, 14 March 2007

Line 23:

==Algorithms==

The easiest way to construct a suffix array is to use an efficient [[comparison sort]] algorithm. This requires <math>O(n \log n)</math> suffix comparisons, but a suffix comparison requires <math>O(n)</math> time, so the overall runtime of this approach is <math>O(n^2 \log n)</math>. More sophisticated algorithms improve this to <math>O(n \log n)</math> by exploiting the results of partial sorts to avoid redundant comparisons. Several <math>\Theta(n)</math> algorithms arehave known,also butbeen aredeveloped rarelywhich usedprovide infaster practiceconstruction becauseand ofhave complexity,space highusage memory requirements, and inefficiencyof <math>O(high constant factorsn)</math>.

==Applications==