Content deleted Content added
m Task 18 (cosmetic): eval 22 templates: del empty params (1×); del |ref=harv (17×); |
Adding short explanation of generalized suffix arrays. |
||
Line 179:
In practical [[open source]] work, a commonly used routine for suffix array construction was qsufsort, based on the 1999 Larsson-Sadakane algorithm.<ref>{{cite journal |last1=Larsson |first1=N. Jesper |last2=Sadakane |first2=Kunihiko |title=Faster suffix sorting |journal=Theoretical Computer Science |date=22 November 2007 |volume=387 |issue=3 |pages=258–272 |doi=10.1016/j.tcs.2007.07.017 |language=en |issn=0304-3975}}</ref> This routine has been superseded by Yuta Mori's DivSufSort, "the fastest known suffix sorting algorithm in main memory" as of 2017. It too can be modified to compute an LCP array. It uses a induced copying combined with Itoh-Tanaka.<ref>{{cite journal |last1=Fischer |first1=Johannes |last2=Kurpicz |first2=Florian |title=Dismantling DivSufSort |arxiv=1710.01896 |date=5 October 2017 |journal=Proceedings of the Prague Stringology Conference 2017}}</ref>
== Generalized Suffix Array ==
The concept of a suffix array can be extended to more than one string. This is called a generalized suffix array (or GSA), a suffix array that contains all suffixes for a set of strings (for example, <math>S=S_1,S_2,S_3,...,S_k</math> and is lexicographically sorted with all suffixes of each string.<ref>{{Citation|last1=Shi|first1=Fei|title=Suffix arrays for multiple strings: A method for on-line multiple string searches.|date=1996|work=Lecture Notes in Computer Science|publisher=Springer Berlin Heidelberg|volume=1179|doi=10.1007/BFb0027775|isbn=978-3-540-62031-0}}</ref>
== Applications ==
| |||