Linear-Time Search in Suffix Arrays
Sin Jeong SeoP, Kim Dong Kyue, Heejin Park, Kunsoo Park · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2005
To search a pattern P in a text, such index data structures as suffix trees and suffix arrays are widely used in diverse applications of string processing and computational biology. It is well known that searching in suffix trees is faster than suffix ways in the aspect of time complexity, i.e., it takes O() time to search P on a constant-size alphabet in a suffix tree while it takes O() time in a suffix way where n is the length of the text. In this paper we present a linear-tim8 search algorithm in suffix arrays for constant-size alphabets. For a gene.al alphabet , it takes O() time.