The Prague Stringology Conference 2006
Pierre Peterlongo, Julien Allali and Marie-France Sagot
The Gapped-Factor Tree
| Abstract: |
| We present a data structure to index a specific kind of factors, that is of substrings, called gapped-factors. A gapped-factor is a factor containing a gap that is ignored during the indexation. The data structure presented is based on the suffix tree and indexes all the gapped-factors of a text with a fixed size of gap, and only those. The construction of this data structure is done online in O(n |Σ|)$ time and space, with n the length of the text and |Σ| the size of the alphabet. Such a data structure may play an important role in some pattern matching and motif inference problems, for instance in text filtration. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |