Indexing Factors with Gaps
Indexing of factors or substrings is a widely used and useful technique in stringology and can be seen as a tool in solving diverse text algorithmic problems. A gapped-factor is a concatenation of a factor of length k, a gap of length d and another factor of length k'. Such a gapped factor is called a (k-d-k')-gapped-factor. The problem of indexing the gapped-factors was considered recently by Peterlongo et al. (In: Stringology, pp. 182-196, 2006). In particular, Peterlongo et al. devised a data structure, namely a gapped factor tree (GFT) to index the gapped-factors. Given a text T of length n over the alphabet Sigma and the values of the parameters k, d and k', the construction of GFT requires O(n vertical bar Sigma vertical bar) time. Once GFT is constructed, a given (k-d-k')-gapped-factor can be reported in O(k+k'+Occ) time, where Occ is the number of occurrences of that factor in T. In this paper, we present a new improved indexing scheme for the gapped-factors. The improvements we achieve come from two aspects. Firstly, we generalize the indexing data structure in the sense that, unlike GFT, it is independent of the parameters k and k'. Secondly, our data structure can be constructed in O(n log(1+epsilon) n) time and space, where 0 < epsilon < 1. The only price we pay is a slight increase, i.e. an additional log log n term, in the query time.
algorithms gapped-factor data structure string index suffix tree