Revision as of 17:24, 21 March 2024 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,660 edits somewhat less vague shortdesc ← Previous edit		Revision as of 13:12, 14 May 2024 edit undo A3nm (talk \| contribs) Extended confirmed users, Pending changes reviewers 4,580 edits do not link to redirect to same page Tag: 2017 wikitext editor Next edit →
Line 27: {{harvtxt\|Li\|Li\|Huo\|2016}} gave the first in-place <math>\mathcal{O}(n)</math> time suffix array construction algorithm that is optimal both in time and space, where ''in-place'' means that the algorithm only needs <math>\mathcal{O}(1)</math> additional space beyond the input string and the output suffix array. [[Enhanced suffix ~~array]]s~~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 [[sparse suffix array]].{{sfn\|I\|Kärkkäinen\|Kempa\|2014}} Multiple probabilistic algorithms have been developed to minimize the additional memory usage including an optimal time and memory algorithm.{{sfn\|Gawrychowski\|Kociumaka\|2017}}

Suffix array: Difference between revisions