zbMATH — the first resource for mathematics

Position-restricted substring searching over small alphabets. (English) Zbl 1375.68230
Summary: We consider the problem of indexing a given text \(T[0\ldots n-1]\) of \(n\) characters over an alphabet set \(\Sigma\) of size \(\sigma\), in order to answer the position-restricted substring searching queries. The query input consists of a pattern \(P\) (of length \(p\)) and two indices \(\ell\) and \(r\) and the output is the set of all \(\mathrm{occ}_{\ell,r}\) occurrences of \(P\) in \(T[\ell \ldots r]\). In this paper, we propose an \(O(n\log \sigma)\)-word space index with \(O(p+\mathrm{occ}_{\ell,r}\log \log n)\) query time. Our solution is interesting when the alphabet size is small. For example, when the alphabet set is of constant size, we achieve significant improvement over the previously best-known linear space index by Y. Nekrich and G. Navarro [Lect. Notes Comput. Sci. 7357, 271–282 (2012; Zbl 1347.68343)] with \(O(p+\mathrm{occ}_{\ell,r}\log^\epsilon n)\) query time, where \(\epsilon>0\) is an arbitrarily small positive constant.

68W32 Algorithms on strings
68P20 Information storage and retrieval of data
Full Text: DOI
[1] Amir, Amihood; Farach, Martin; Idury, Ramana M.; Lapoutre, Johannes A.; Schaffer, Alejandro A., Improved dynamic dictionary matching, Inf. Comput., 119, 2, 258-282, (1995) · Zbl 0832.68033
[2] Bille, Philip; Gørtz, Inge Li, Substring range reporting, Algorithmica, 69, 2, 384-396, (2014) · Zbl 1360.68375
[3] Biswas, Sudip; Ku, Tsung-Han; Shah, Rahul; Thankachan, Sharma V., Position-restricted substring searching over small alphabets, (String Processing and Information Retrieval, (2013), Springer), 29-36 · Zbl 1375.68230
[4] Chan, Timothy M.; Larsen, Kasper Green; Pătraşcu, Mihai, Orthogonal range searching on the ram, revisited, (Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, (2011), ACM), 1-10 · Zbl 1283.68139
[5] Chien, Yu-Feng; Hon, Wing-Kai; Shah, Rahul; Thankachan, Sharma V.; Vitter, Jeffrey Scott, Geometric bwt: compressed text indexing via sparse suffixes and range searching, Algorithmica, 1-21, (2013) · Zbl 1314.68115
[6] Cohen, Hagai; Porat, Ely, Range non-overlapping indexing, (International Symposium on Algorithms and Computation, (2009), Springer), 1044-1053 · Zbl 1273.68097
[7] Crochemore, Maxime; Iliopoulos, Costas S.; Kubica, Marcin; Rahman, M. Sohel; Tischler, German; Waleń, Tomasz, Improved algorithms for the range next value problem and applications, Theor. Comput. Sci., 434, 23-34, (2012) · Zbl 1244.68031
[8] Gagie, Travis; Gawrychowski, Paweł, Linear-space substring range counting over polylogarithmic alphabets, (2012), preprint
[9] Ganguly, Arnab; Shah, Rahul; Thankachan, Sharma V., Succinct non-overlapping indexing, (Annual Symposium on Combinatorial Pattern Matching, (2015), Springer), 185-195 · Zbl 1432.68089
[10] Golynski, Alexander; Munro, J. Ian; Rao, S. Srinivasa, Rank/select operations on large alphabets: a tool for text indexing, (Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, (2006), ACM), 368-373 · Zbl 1192.68800
[11] Hon, Wing-Kai; Shah, Rahul; Thankachan, Sharma V.; Vitter, Jeffrey Scott, On position restricted substring searching in succinct space, J. Discret. Algorithms, 17, 109-114, (2012) · Zbl 1267.68102
[12] Keller, Orgad; Kopelowitz, Tsvi; Lewenstein, Moshe, Range non-overlapping indexing and successive List indexing, (Workshop on Algorithms and Data Structures, (2007), Springer), 625-636 · Zbl 1209.68160
[13] Kopelowitz, Tsvi; Lewenstein, Moshe; Porat, Ely, Persistency in suffix trees with applications to string interval problems, (String Processing and Information Retrieval, (2011), Springer), 67-80
[14] Mäkinen, Veli; Navarro, Gonzalo, Position-restricted substring searching, (LATIN 2006: Theoretical Informatics, (2006), Springer), 703-714 · Zbl 1145.68392
[15] Manber, Udi; Myers, Gene, Suffix arrays: a new method for on-line string searches, SIAM J. Comput., 22, 5, 935-948, (1993) · Zbl 0784.68027
[16] McCreight, Edward M., A space-economical suffix tree construction algorithm, J. ACM, 23, 2, 262-272, (1976) · Zbl 0329.68042
[17] Nekrich, Yakov; Navarro, Gonzalo, Sorted range reporting, (Algorithm Theory - SWAT 2012, (2012), Springer), 271-282 · Zbl 1347.68343
[18] Weiner, Peter, Linear pattern matching algorithms, (IEEE Conference Record of 14th Annual Symposium on Switching and Automata Theory, SWAT’08, 1973, (1973), IEEE), 1-11
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.