New suffix array algorithms - linear but not fast?
In 2003 three (-)(n)-time algorithms were proposed for the construction of a suffix array of a string x = x[1..n] on an indexed alphabet, all of them inspired by the methodology of Farach's (-)(n)- time suffix tree construction algorithm. In the same year a (-)(m)-time algorithm was described f...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Published: |
Australian Computer Society
2004
|
| Online Access: | http://hdl.handle.net/20.500.11937/36803 |
| _version_ | 1848754871527800832 |
|---|---|
| author | Antonitio, A. Ryan, P. Smyth, Bill Turpin, A. Yu, X. |
| author2 | Seok-Hee Hong |
| author_facet | Seok-Hee Hong Antonitio, A. Ryan, P. Smyth, Bill Turpin, A. Yu, X. |
| author_sort | Antonitio, A. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | In 2003 three (-)(n)-time algorithms were proposed for the construction of a suffix array of a string x = x[1..n] on an indexed alphabet, all of them inspired by the methodology of Farach's (-)(n)- time suffix tree construction algorithm. In the same year a (-)(m)-time algorithm was described for computing all the occurrences of a pattern p = p[1..m] in x, given a suffix array of x and various other (-)(n) - space data structures. We analyze the effectiveness and limitations of these algorithms, especially in terms of execution time, and we discuss strategies for their improvement. |
| first_indexed | 2025-11-14T08:47:18Z |
| format | Conference Paper |
| id | curtin-20.500.11937-36803 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:47:18Z |
| publishDate | 2004 |
| publisher | Australian Computer Society |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-368032017-10-02T02:27:39Z New suffix array algorithms - linear but not fast? Antonitio, A. Ryan, P. Smyth, Bill Turpin, A. Yu, X. Seok-Hee Hong In 2003 three (-)(n)-time algorithms were proposed for the construction of a suffix array of a string x = x[1..n] on an indexed alphabet, all of them inspired by the methodology of Farach's (-)(n)- time suffix tree construction algorithm. In the same year a (-)(m)-time algorithm was described for computing all the occurrences of a pattern p = p[1..m] in x, given a suffix array of x and various other (-)(n) - space data structures. We analyze the effectiveness and limitations of these algorithms, especially in terms of execution time, and we discuss strategies for their improvement. 2004 Conference Paper http://hdl.handle.net/20.500.11937/36803 Australian Computer Society fulltext |
| spellingShingle | Antonitio, A. Ryan, P. Smyth, Bill Turpin, A. Yu, X. New suffix array algorithms - linear but not fast? |
| title | New suffix array algorithms - linear but not fast? |
| title_full | New suffix array algorithms - linear but not fast? |
| title_fullStr | New suffix array algorithms - linear but not fast? |
| title_full_unstemmed | New suffix array algorithms - linear but not fast? |
| title_short | New suffix array algorithms - linear but not fast? |
| title_sort | new suffix array algorithms - linear but not fast? |
| url | http://hdl.handle.net/20.500.11937/36803 |