Name
Abstract | ||
|---|---|---|
We address the problem of finding the locations of all instances of a string P in a text T, where preprocessing of T is allowed in order to facilitate the queries. Previous data structures for this problem include the suffix tree, the suffix array, and the compact DAWG. We modify a data structure called a sequence tree, which was proposed by Coffman and Eve (1970) [3] for hashing, and adapt it to the new problem. We can then produce a list of k occurrences of any string P in T in O(@?P@?+k) time. Because of properties shared by suffixes of a text that are not shared by arbitrary hash keys, we can build the structure in O(@?T@?) time, which is much faster than Coffman and Eve's algorithm. These bounds are as good as those for the suffix tree, suffix array, and the compact DAWG. The advantages are the elementary nature of some of the algorithms for constructing and using the data structure and the asymptotic bounds we can give for updating the data structure when the text is edited. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.jda.2010.12.001 | J. Discrete Algorithms |
Keywords | Field | DocType |
elementary nature,position heap,new problem,compact dawg,dynamic text indexing data,data structure,arbitrary hash key,sequence tree,suffix array,suffix tree,string p,string searching,previous data structure | String searching algorithm,Discrete mathematics,Data structure,Combinatorics,Computer science,Suffix array,Generalized suffix tree,Suffix tree,FM-index,Compressed suffix array,Longest common substring problem | Journal |
Volume | Issue | ISSN |
9 | 1 | Journal of Discrete Algorithms |
Citations | PageRank | References |
14 | 0.78 | 9 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrzej Ehrenfeucht | 1 | 1339 | 537.91 |
| R McConnell | 2 | 825 | 66.28 |
| Nissa Osheim | 3 | 24 | 2.07 |
| Sung-Whan Woo | 4 | 50 | 3.47 |