New suffix array algorithms - linear but not fast?
| dc.contributor.author | Antonitio, A. | |
| dc.contributor.author | Ryan, P. | |
| dc.contributor.author | Smyth, Bill | |
| dc.contributor.author | Turpin, A. | |
| dc.contributor.author | Yu, X. | |
| dc.contributor.editor | Seok-Hee Hong | |
| dc.date.accessioned | 2017-01-30T13:57:47Z | |
| dc.date.available | 2017-01-30T13:57:47Z | |
| dc.date.created | 2010-04-01T20:02:07Z | |
| dc.date.issued | 2004 | |
| dc.identifier.citation | Antonitio, A. and Ryan, P. and Smyth, W. and Turpin, A. and Yu, X. 2004. New suffix array algorithms - linear but not fast?, in Hong, S. (ed), 15th Australasian Workshop on Combinatorial Algorithms (AWOCA), pp. 148-156. Ballina, Australia: Australian Computer Society. | |
| dc.identifier.uri | http://hdl.handle.net/20.500.11937/36803 | |
| dc.description.abstract |
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. | |
| dc.publisher | Australian Computer Society | |
| dc.title | New suffix array algorithms - linear but not fast? | |
| dc.type | Conference Paper | |
| dcterms.source.startPage | 148 | |
| dcterms.source.endPage | 156 | |
| dcterms.source.title | Proceedings of the 15th Australasian workshop on combinatorial algorithms (AWOCA) | |
| dcterms.source.series | Proceedings of the 15th Australasian workshop on combinatorial algorithms (AWOCA) | |
| dcterms.source.conference | 15th Australasian Workshop on Combinatorial Algorithms (AWOCA) | |
| dcterms.source.conference-start-date | Jul 7 2004 | |
| dcterms.source.conferencelocation | Ballina, Australia | |
| dcterms.source.place | Australia | |
| curtin.accessStatus | Open access | |
| curtin.faculty | School of Science and Computing | |
| curtin.faculty | Department of Computing | |
| curtin.faculty | Faculty of Science and Engineering |