Content deleted Content added
Updated citation for definition of a "sparse suffix array". The previous citation did not contain any mention of the term "sparse suffix array" at all. Do note that Tomohiro I's surname really is "I" per his webpage at http://www.donald.ai.kyutech.ac.jp/~tomohiro/index_e.html - it's not short for "the first" like in the name of a king! |
Hkgarcon00 (talk | contribs) m edit header format |
||
Line 260:
By performing a bottom-up traversal of the lcp-interval of the tree, the child table can be constructed in linear time. The ''up/down'' values and the ''nextlIndex'' values can be computed separately by using two distinct algorithms.
== Constructing a Suffix Link Table ==
The suffix links for an enhanced suffix array can be computed by generating the suffix link interval [''1,..,r''] for each [i,..j] interval during the preprocessing. The left and right elements l and r of the interval are maintained in the first index of [i,..,j]. The table for this interval ranges from 0 to n. The suffix link table is constructed by the left-to-right breadth-first traversal of the lcp-interval tree. Every time an ''l''-interval is computed, it is added to the list of l-intervals, which is referred to as the l-list. When the lcp-value > 0, for every ''l''-interval[i,..,j] in the list, link[i] is calculated. The interval [''l'',..,''r''] is computed by a binary search in(''l''-1)-list, where ''l'' is the largest left boundary amongst all the ''l''-1 intervals. The suffix link interval of [i,..j] is represented by this interval[''l,..,r'']. The values ''l'' and ''r'' are ultimately stored in the first index of [i,..,j].
| |||