{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T17:13:22Z","timestamp":1770484402380,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642192210","type":"print"},{"value":"9783642192227","type":"electronic"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-19222-7_10","type":"book-chapter","created":{"date-parts":[[2011,3,14]],"date-time":"2011-03-14T08:03:12Z","timestamp":1300089792000},"page":"90-102","source":"Crossref","is-referenced-by-count":5,"title":["Worst Case Efficient Single and Multiple String Matching in the RAM Model"],"prefix":"10.1007","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"6","key":"10_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A.V. Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: An aid to bibliographic search. ACM Commun.\u00a018(6), 333\u2013340 (1975)","journal-title":"ACM Commun."},{"issue":"5","key":"10_CR2","first-page":"1209","volume":"11","author":"V.L. Arlazarov","year":"1970","unstructured":"Arlazarov, V.L., Dinic, E.A., Kronrod, M.A., Faradzev, I.A.: On economical construction of the transitive closure of a directed graph. Soviet Mathematics Doklady\u00a011(5), 1209\u20131210 (1970)","journal-title":"Soviet Mathematics Doklady"},{"key":"10_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-642-13509-5_9","volume-title":"Combinatorial Pattern Matching","author":"D. Belazzougui","year":"2010","unstructured":"Belazzougui, D.: Succinct dictionary matching with no slowdown. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol.\u00a06129, pp. 88\u2013100. Springer, Heidelberg (2010)"},{"key":"10_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/978-3-642-02441-2_11","volume-title":"Combinatorial Pattern Matching","author":"P. Bille","year":"2009","unstructured":"Bille, P.: Fast searching in packed strings. In: Kucherov, G., Ukkonen, E. (eds.) CPM 2009. LNCS, vol.\u00a05577, pp. 116\u2013126. Springer, Heidelberg (2009)"},{"issue":"10","key":"10_CR5","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R.S. Boyer","year":"1977","unstructured":"Boyer, R.S., Moore, J.S.: A fast string searching algorithm. ACM Commun.\u00a020(10), 762\u2013772 (1977)","journal-title":"ACM Commun."},{"issue":"3","key":"10_CR6","doi-asserted-by":"publisher","first-page":"703","DOI":"10.1137\/0215051","volume":"15","author":"B. Chazelle","year":"1986","unstructured":"Chazelle, B.: Filtering search: A new approach to query-answering. SIAM J. Comput.\u00a015(3), 703\u2013724 (1986)","journal-title":"SIAM J. Comput."},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Chien, Y.-F., Hon, W.-K., Shah, R., Vitter, J.S.: Geometric Burrows-Wheeler transform: Linking range searching and text indexing. In: DCC, pp. 252\u2013261 (2008)","DOI":"10.1109\/DCC.2008.67"},{"issue":"4\/5","key":"10_CR8","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF01185427","volume":"12","author":"M. Crochemore","year":"1994","unstructured":"Crochemore, M., Czumaj, A., Gasieniec, L., Jarominek, S., Lecroq, T., Plandowski, W., Rytter, W.: Speeding up two string-matching algorithms. Algorithmica\u00a012(4\/5), 247\u2013267 (1994)","journal-title":"Algorithmica"},{"key":"10_CR9","volume-title":"Text Algorithms","author":"M. Crochemore","year":"1994","unstructured":"Crochemore, M., Rytter, W.: Text Algorithms. Oxford University Press, Oxford (1994)"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Gil, J., Matias, Y., Pippenger, N.: Polynomial hash functions are reliable (extended abstract). In: ICALP, pp. 235\u2013246 (1992)","DOI":"10.1007\/3-540-55719-9_77"},{"issue":"2","key":"10_CR11","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/301970.301973","volume":"46","author":"P. Ferragina","year":"1999","unstructured":"Ferragina, P., Grossi, R.: The string b-tree: A new data structure for string search in external memory and its applications. J. ACM\u00a046(2), 236\u2013280 (1999)","journal-title":"J. ACM"},{"issue":"3","key":"10_CR12","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with 0(1) worst case access time. J. ACM\u00a031(3), 538\u2013544 (1984)","journal-title":"J. ACM"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/3-540-45735-6_5","volume-title":"String Processing and Information Retrieval","author":"K. Fredriksson","year":"2002","unstructured":"Fredriksson, K.: Faster string matching with super-alphabets. In: Laender, A.H.F., Oliveira, A.L. (eds.) SPIRE 2002. LNCS, vol.\u00a02476, pp. 44\u201357. Springer, Heidelberg (2002)"},{"key":"10_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/3-540-44693-1_28","volume-title":"STACS 2001","author":"T. Hagerup","year":"2001","unstructured":"Hagerup, T., Tholey, T.: Efficient minimal perfect hashing in nearly minimal space. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol.\u00a02010, pp. 317\u2013326. Springer, Heidelberg (2001)"},{"issue":"2","key":"10_CR15","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput.\u00a06(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"10_CR16","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: Suffix arrays: A new method for on-line string searches. SIAM J. Comput.\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10_CR17","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/S1570-8667(03)00066-2","volume":"2","author":"G. Navarro","year":"2004","unstructured":"Navarro, G.: Indexing text using the ziv-lempel trie. J. Discrete Algorithms\u00a02(1), 87\u2013114 (2004)","journal-title":"J. Discrete Algorithms"},{"key":"10_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1007\/BFb0030778","volume-title":"Combinatorial Pattern Matching","author":"G. Navarro","year":"1998","unstructured":"Navarro, G., Raffinot, M.: A bit-parallel approach to suffix automata: Fast extended string matching. In: Farach-Colton, M. (ed.) CPM 1998. LNCS, vol.\u00a01448, pp. 14\u201333. Springer, Heidelberg (1998)"},{"key":"10_CR19","doi-asserted-by":"crossref","unstructured":"Patrascu, M.: (data) structures. In: FOCS, pp. 434\u2013443 (2008)","DOI":"10.1109\/FOCS.2008.69"},{"key":"10_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-642-04241-6_21","volume-title":"Algorithms in Bioinformatics","author":"E. Rivals","year":"2009","unstructured":"Rivals, E., Salmela, L., Kiiskinen, P., Kalsi, P., Tarhio, J.: mpscan: Fast localisation of multiple reads in genomes. In: Salzberg, S.L., Warnow, T. (eds.) WABI 2009. LNCS, vol.\u00a05724, pp. 246\u2013260. Springer, Heidelberg (2009)"},{"key":"10_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-642-03784-9_5","volume-title":"String Processing and Information Retrieval","author":"A. Tam","year":"2009","unstructured":"Tam, A., Wu, E., Lam, T.W., Yiu, S.-M.: Succinct text indexing with wildcards. In: Karlgren, J., Tarhio, J., Hyyr\u00f6, H. (eds.) SPIRE 2009. LNCS, vol.\u00a05721, pp. 39\u201350. Springer, Heidelberg (2009)"},{"key":"10_CR22","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01683268","volume":"10","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and implementation of an efficient priority queue. Mathematical Systems Theory\u00a010, 99\u2013127 (1977)","journal-title":"Mathematical Systems Theory"},{"issue":"2","key":"10_CR23","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D.E. Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space theta(n). Inf. Process. Lett.\u00a017(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"10_CR24","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1137\/0208029","volume":"8","author":"A.C.-C. Yao","year":"1979","unstructured":"Yao, A.C.-C.: The complexity of pattern matching for a random string. SIAM J. Comput.\u00a08(3), 368\u2013387 (1979)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-19222-7_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T10:41:57Z","timestamp":1558435317000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-19222-7_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642192210","9783642192227"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-19222-7_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011]]}}}