Revision as of 08:21, 19 April 2025 edit Rcfische2 (talk \| contribs) 367 edits m Serves me right for not using preview ← Previous edit		Revision as of 11:02, 23 April 2025 edit undo 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? Next edit →
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 [[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}}~~ == Definition == Line 288: \| author2-link = Gene Myers }} * {{Cite journal\|last1=Gawrychowski\|first1=Paweł\|last2=Kociumaka\|first2=Tomasz\|date=January 2017 \|title=Sparse Suffix Tree Construction in Optimal Time and Space\|journal=Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms\|___location=Philadelphia, PA\|publisher=Society for Industrial and Applied Mathematics\|pages=425–439\|isbn=9781611974782\|arxiv=1608.00865\|doi=10.1137/1.9781611974782.27 \|s2cid=6608776}} * {{cite conference \|last1=Li\|first1=Zhize\|last2=Li\|first2=Jian\|last3=Huo\|first3=Hongwei \|doi = 10.1007/978-3-030-00479-8_22

Suffix array: Difference between revisions