Position-restricted substring searching. (English) Zbl 1145.68392

Correa, José R. (ed.) et al., LATIN 2006: Theoretical informatics. 7th Latin American symposium, Valdivia, Chile, March 20–24, 2006. Proceedings. Berlin: Springer (ISBN 3-540-32755-X/pbk). Lecture Notes in Computer Science 3887, 703-714 (2006).
Summary: A full-text index is a data structure built over a text string \(T[1,n]\). The most basic functionality provided is \((a)\) counting how many times a pattern string \(P[1,m]\) appears in \(T\) and \((b)\) locating all those \(occ\) positions. There exist several indexes that solve \((a)\) in \(O(m)\) time and \((b)\) in \(O(occ)\) time. In this paper we propose two new queries, \((c)\) counting how many times \(P[1,m]\) appears in \(T[l,r]\) and \((d)\) locating all those \(occ_{l,r}\) positions. These can be solved using \((a)\) and \((b)\) but this requires \(O(occ)\) time. We present two solutions to \((c)\) and \((d)\) in this paper. The first is an index that requires \(O(n \log n)\) bits of space and answers \((c)\) in \(O(m+\log n)\) time and \((d)\) in \(O(\log n)\) time per occurrence (that is, \(O(occ_{l,r} \log n)\) time overall). A variant of the first solution answers \((c)\) in \(O(m+\log \log n)\) time and \((d)\) in constant time per occurrence, but requires \(O(n\log ^{1+\epsilon } n)\) bits of space for any constant \(\epsilon > 0\). The second solution requires \(O(n m \log \sigma )\) bits of space, solving \((c)\) in \(O(m \lceil \log \sigma / \log \log n \rceil )\) time and \((d)\) in \(O(m \lceil \log \sigma / \log \log n \rceil )\) time per occurrence, where \(\sigma \) is the alphabet size. This second structure takes less space when the text is compressible.
Our solutions can be seen as a generalization of rank and select dictionaries, which allow computing how many times a given character \(c\) appears in a prefix \(T[1,i]\) and also locate the \(i\)-th occurrence of \(c\) in \(T\). Our solution to \((c)\) extends character rank queries to substring rank queries, and our solution to \((d)\) extends character select to substring select queries.
As a byproduct, we show how rank queries can be used to implement fractional cascading in little space, so as to obtain an alternative implementation of a well-known two-dimensional range search data structure by Chazelle. We also show how Grossi et al.’s wavelet trees are suitable for two-dimensional range searching, and their connection with Chazelle’s data structure.
For the entire collection see [Zbl 1096.68003].


68P05 Data structures
68P10 Searching and sorting
68W05 Nonnumerical algorithms
Full Text: DOI Link