返回Google圖書搜尋

Suffix Arrays

其他書名	A New Method for On-line String Searches
出版	University of Arizona, Department of Computer Science, 1989
URL	http://books.google.com.hk/books?id=VP-iPgAACAAJ&hl=&source=gbs_api

註釋Abstract: "A new and conceptually simple data structure, called a suffix array, for on-line string searches is introduced in this paper. Constructing and querying suffix arrays is reduced to a sort and search paradigm that employs novel algorithms. The main advantage of suffix arrays over suffix trees is that they are three to five times more space efficient. Suffix arrays permit on-line string searches of the type, 'Is W a substring of A?' to be answered in time O(P+logN), where P is the length of W and N is the length of A, which is competitive with (and in some cases slightly better than) suffix trees.