Suffix array: Difference between revisions

Browse history interactively

← Previous edit

Content deleted Content added

VisualWikitext

Revision as of 11:02, 23 April 2025 edit ExplodingCabbage (talk \| contribs) Extended confirmed users 840 edits 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? ← Previous edit		Latest revision as of 03:37, 11 August 2025 edit undo Bender the Bot (talk \| contribs) Bots 1,064,377 edits m →External links: HTTP to HTTPS for SourceForge Tag: AWB
(2 intermediate revisions by one other user not shown)
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~~A ~~suffix~~sorted array ~~for~~of aonly ~~subset~~some of(rather than all) suffixes of a string is called a [[sparse suffix array]].{{sfn\|I\|Kärkkäinen\|Kempa\|2014}} == Definition == Line 376: * [http://code.google.com/p/compression-code/downloads/list Suffix sorting module for BWT in C code] * [http://www.codeodor.com/index.cfm/2007/12/24/The-Suffix-Array/1845 Suffix Array Implementation in Ruby] * [~~http~~https://sary.sourceforge.net/index.html.en Suffix array library and tools] * [http://pizzachili.dcc.uchile.cl/ Project containing various Suffix Array c/c++ Implementations with a unified interface] * [https://github.com/y-256/libdivsufsort A fast, lightweight, and robust C API library to construct the suffix array]