Content deleted Content added
→Algorithms: please add a direct reference to the papers that introduce efficient suffix array construction algorithms |
m Date the maintenance tags or general fixes |
||
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 have also been developed which provide faster construction and have space usage of <math>O(n)</math> with low constants.{{
==Applications==
Line 47:
*[http://www.codeodor.com/index.cfm/2007/12/24/The-Suffix-Array/1845 Suffix Array Implementation in Ruby]
*[http://sary.sourceforge.net/ Suffix array library and tools]
[[Category:Arrays]]
[[Category:Algorithms on strings]]
| |||