Content deleted Content added
adding information. |
No edit summary |
||
Line 35:
To find a given substring X, two binary searches are used to find the range of suffixes prefixed by X. To gain efficiency, the string comparisons in the binary searches are modified to take advantage of longest common prefixes (LCP's) as the search narrows. The output of the search is the list of starting positions for the suffixes prefixed by X.
In 2004, Ko et al presented an algorithm for constructing a suffix array "de novo" in time proportional to the length of the string. Suffix arrays may be converted to [{Suffix tree]]s in linear time as well. ▼
The key insight of the suffix array is to denote each suffix by its starting position only (the left column above). The resultant array of numbers, combined with the original string, is a compact representation of the sorted suffix list, consuming one character and one integer for each character in the string.
▲In 2004, Ko et al presented an algorithm for constructing a suffix array
| |||