Content deleted Content added
Removed Gawrychowski & Kociumaka cite. I don't see how their algorithms - all with worse than O(n) time complexity and limited to integer alphabets - can *possibly* be "optimal" as claimed here, since in the preceding paragraph we noted a COMPLETE suffix array can be computed in O(n) time and it's obviously only a further O(n) operation to filter that result down to a sparse suffix array. I have not studied the papers closely but surely the optimality claim just trivially cannot be true? |
m grammar/typo fix |
||
Line 28:
Enhanced suffix arrays (ESAs) are suffix arrays with additional tables that reproduce the full functionality of suffix trees preserving the same time and memory complexity.{{sfn|Abouelhoda|Kurtz|Ohlebusch|2004}}
The suffix array for a subset of all suffixes of a string is called a [[sparse suffix array]].{{sfn|I|Kärkkäinen|Kempa|2014}}
== Definition ==
| |||