Worst-case efficient single and multiple string matching on packed texts in the word-RAM model

Aho, 1975, Efficient string matching: An aid to bibliographic search, Commun. ACM, 18, 333, 10.1145/360825.360855 Andersson, 1998, Sorting in linear time?, J. Comput. System Sci., 57, 74, 10.1006/jcss.1998.1580 Arlazarov, 1970, On economical construction of the transitive closure of a directed graph, Soviet Math. Dokl., 11, 1209 D. Belazzougui, Succinct dictionary matching with no slowdown, in: CPM, 2010, pp. 88–100. O. Ben-kiki, P. Bille, D. Breslauer, R. Grossi, O. Weimann, Optimal packed string matching, in: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2011. P. Bille, Fast searching in packed strings, in: CPM, 2009, pp. 116–126. Boyer, 1977, A fast string searching algorithm, Commun. ACM, 20, 762, 10.1145/359842.359859 A. Brodnik, Computation of the least significant set bit, in: Proceedings of the 2nd Electrotechnical and Computer Science Conference, Portoroz, 1993, pp. 7–10. Chazelle, 1986, Filtering search: A new approach to query-answering, SIAM J. Comput., 15, 703, 10.1137/0215051 Y.-F. Chien, W.-K. Hon, R. Shah, J.S. Vitter, Geometric Burrows-Wheeler transform: Linking range searching and text indexing, in: DCC, 2008, pp. 252–261. Crochemore, 1994, Speeding up two string-matching algorithms, Algorithmica, 12, 247, 10.1007/BF01185427 Crochemore, 2007 Crochemore, 1994 M. Dietzfelbinger, J. Gil, Y. Matias, N. Pippenger, Polynomial hash functions are reliable (extended abstract), in: ICALP, 1992, pp. 235–246. Ferragina, 1999, The string B-tree: A new data structure for string search in external memory and its applications, J. ACM, 46, 236, 10.1145/301970.301973 Fredman, 1984, Storing a sparse table with 0(1) worst case access time, J. ACM, 31, 538, 10.1145/828.1884 Fredman, 1993, Surpassing the information theoretic bound with fusion trees, J. Comput. System Sci., 47, 424, 10.1016/0022-0000(93)90040-4 K. Fredriksson, Faster string matching with super-alphabets, in: SPIRE, 2002, pp. 44–57. Grossi, 2005, Compressed suffix arrays and suffix trees with applications to text indexing and string matching, SIAM J. Comput., 35, 378, 10.1137/S0097539702402354 T. Hagerup, T. Tholey, Efficient minimal perfect hashing in nearly minimal space, in: STACS, 2001, pp. 317–326. Intel, 2011 Knuth, 1977, Fast pattern matching in strings, SIAM J. Comput., 6, 323, 10.1137/0206024 R.M. Kolpakov, G. Kucherov, Finding maximal repetitions in a word in linear time, in: FOCS, 1999, pp. 596–604. Manber, 1993, Suffix arrays: A new method for on-line string searches, SIAM J. Comput., 22, 935, 10.1137/0222058 Navarro, 2004, Indexing text using the Ziv–Lempel trie, J. Discrete Algorithms, 2, 87, 10.1016/S1570-8667(03)00066-2 G. Navarro, M. Raffinot, A bit-parallel approach to suffix automata: Fast extended string matching, in: CPM, 1998, pp. 14–33. M. Patrascu, (data) structures, in: FOCS, 2008, pp. 434–443. E. Rivals, L. Salmela, P. Kiiskinen, P. Kalsi, J. Tarhio, MPSCAN, Fast localisation of multiple reads in genomes, in: WABI, 2009, pp. 246–260. A. Tam, E. Wu, T.W. Lam, S.-M. Yiu, Succinct text indexing with wildcards, in: SPIRE, 2009, pp. 39–50. van Emde Boas, 1977, Design and implementation of an efficient priority queue, Math. Systems Theory, 10, 99, 10.1007/BF01683268 Willard, 1983, Log-logarithmic worst-case range queries are possible in space θ(n), Inform. Process. Lett., 17, 81, 10.1016/0020-0190(83)90075-3 Yao, 1979, The complexity of pattern matching for a random string, SIAM J. Comput., 8, 368, 10.1137/0208029