{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T05:05:37Z","timestamp":1761973537481,"version":"build-2065373602"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642382321"},{"type":"electronic","value":"9783642382338"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38233-8_4","type":"book-chapter","created":{"date-parts":[[2013,5,15]],"date-time":"2013-05-15T12:57:16Z","timestamp":1368622636000},"page":"37-48","source":"Crossref","is-referenced-by-count":3,"title":["Average Optimal String Matching in Packed Strings"],"prefix":"10.1007","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mathieu","family":"Raffinot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"4_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. Commun. ACM\u00a018(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"key":"4_CR2","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1006\/jagm.2000.1087","volume":"36","author":"C. Allauzen","year":"2000","unstructured":"Allauzen, C., Raffinot, M.: Simple optimal string matching. Journal of Algorithms\u00a036, 102\u2013116 (2000)","journal-title":"Journal of Algorithms"},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-19222-7_10","volume-title":"Combinatorial Algorithms","author":"D. Belazzougui","year":"2011","unstructured":"Belazzougui, D.: Worst case efficient single and multiple string matching in the ram model. In: Iliopoulos, C.S., Smyth, W.F. (eds.) IWOCA 2010. LNCS, vol.\u00a06460, pp. 90\u2013102. Springer, Heidelberg (2011)"},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jda.2011.12.011","volume":"14","author":"D. Belazzougui","year":"2012","unstructured":"Belazzougui, D.: Worst-case efficient single and multiple string matching on packed texts in the word-ram model. J. Discrete Algorithms\u00a014, 91\u2013106 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Monotone minimal perfect hashing: searching a sorted table with o(1) accesses. In: SODA, pp. 785\u2013794 (2009)","DOI":"10.1137\/1.9781611973068.86"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/978-3-642-15775-2_37","volume-title":"Algorithms \u2013 ESA 2010","author":"D. Belazzougui","year":"2010","unstructured":"Belazzougui, D., Boldi, P., Pagh, R., Vigna, S.: Fast prefix search in little space, with applications. In: de Berg, M., Meyer, U. (eds.) ESA 2010, Part I. LNCS, vol.\u00a06346, pp. 427\u2013438. Springer, Heidelberg (2010)"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-642-16321-0_15","volume-title":"String Processing and Information Retrieval","author":"D. Belazzougui","year":"2010","unstructured":"Belazzougui, D., Boldi, P., Vigna, S.: Dynamic Z-fast tries. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 159\u2013172. Springer, Heidelberg (2010)"},{"key":"4_CR8","unstructured":"Ben-Kiki, O., Bille, P., Breslauer, D., Gasieniec, L., Grossi, R., Weimann, O.: Optimal Packed String Matching. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a013, pp. 423\u2013432 (2011)"},{"key":"4_CR9","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 Lille. LNCS, vol.\u00a05577, pp. 116\u2013126. Springer, Heidelberg (2009)"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/978-3-642-31265-6_7","volume-title":"Combinatorial Pattern Matching","author":"D. Breslauer","year":"2012","unstructured":"Breslauer, D., G\u0105sieniec, L., Grossi, R.: Constant-time word-size string matching. In: K\u00e4rkk\u00e4inen, J., Stoye, J. (eds.) CPM 2012. LNCS, vol.\u00a07354, pp. 83\u201396. Springer, Heidelberg (2012)"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Carter, L., Wegman, M.N.: Universal classes of hash functions (extended abstract). In: STOC, pp. 106\u2013112 (1977)","DOI":"10.1145\/800105.803400"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., Patrascu, M.: Orthogonal range searching on the ram, revisited. In: Symposium on Computational Geometry, pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"issue":"3","key":"4_CR13","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":"4_CR14","unstructured":"Crochemore, M., Czumaj, A., Sieniec, L.G., Jarominek, S., Lecroq, T., Plandowski, W., Rytter, W.: Fast multi-pattern matching. Rapport I.G.M. 93-3, Universit\u00e9 de Marne-la-Vall\u00e9e (1993)"},{"key":"4_CR15","unstructured":"Crochemore, M., Rytter, W.: Text algorithms. Oxford University Press (1994)"},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF01185427","volume":"12","author":"A. Czumaj","year":"1994","unstructured":"Czumaj, A., Crochemore, M., Gasieniec, L., Jarominek, S., Lecroq, T., Plandowski, W., Rytter, W.: Speeding up two string-matching algorithms. Algorithmica\u00a012, 247\u2013267 (1994)","journal-title":"Algorithmica"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: FOCS, pp. 137\u2013143 (1997)","DOI":"10.1109\/SFCS.1997.646102"},{"key":"4_CR18","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)"},{"issue":"2","key":"4_CR19","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R. Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput.\u00a035(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"4_CR20","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/jagm.2001.1171","volume":"41","author":"T. Hagerup","year":"2001","unstructured":"Hagerup, T., Miltersen, P.B., Pagh, R.: Deterministic dictionaries. J. Algorithms\u00a041(1), 69\u201385 (2001)","journal-title":"J. Algorithms"},{"key":"4_CR21","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":"1","key":"4_CR22","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/s00453-006-1228-8","volume":"48","author":"W.-K. Hon","year":"2007","unstructured":"Hon, W.-K., Lam, T.W., Sadakane, K., Sung, W.-K., Yiu, S.-M.: A space and time efficient algorithm for constructing compressed suffix arrays. Algorithmica\u00a048(1), 23\u201336 (2007)","journal-title":"Algorithmica"},{"issue":"6","key":"4_CR23","doi-asserted-by":"publisher","first-page":"2162","DOI":"10.1137\/070685373","volume":"38","author":"W.-K. Hon","year":"2009","unstructured":"Hon, W.-K., Sadakane, K., Sung, W.-K.: Breaking a time-and-space barrier in constructing full-text indices. SIAM J. Comput.\u00a038(6), 2162\u20132178 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"4_CR24","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(1), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"4_CR25","unstructured":"Lecroq, T.: Recherches de mot. Th\u00e8se de doctorat, Universit\u00e9 d\u2019Orl\u00e9ans, France (1992)"},{"issue":"5","key":"4_CR26","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."},{"key":"4_CR27","unstructured":"Morris Jr., J.H., Pratt, V.R.: A linear pattern-matching algorithm. Report\u00a040, University of California, Berkeley (1970)"},{"issue":"4","key":"4_CR28","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"D.R. Morrison","year":"1968","unstructured":"Morrison, D.R.: Patricia-practical algorithm to retrieve information coded in alphanumeric. J. ACM\u00a015(4), 514\u2013534 (1968)","journal-title":"J. ACM"},{"key":"4_CR29","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/351827.384246","volume":"5","author":"G. Navarro","year":"2000","unstructured":"Navarro, G., Raffinot, M.: Fast and flexible string matching by combining bit-parallelism and suffix automata. ACM Journal of Experimental Algorithmics\u00a05, 4 (2000)","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"4_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-540-70575-8_8","volume-title":"Automata, Languages and Programming","author":"M. Ru\u017ei\u0107","year":"2008","unstructured":"Ru\u017ei\u0107, M.: Constructing efficient dictionaries in close to sorting time. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 84\u201395. Springer, Heidelberg (2008)"},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"Ruzic, M.: Making deterministic signatures quickly. ACM Transactions on Algorithms\u00a05(3) (2009)","DOI":"10.1145\/1541885.1541887"},{"issue":"4","key":"4_CR32","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","volume":"41","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theory Comput. Syst.\u00a041(4), 589\u2013607 (2007)","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"4_CR33","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1137\/0208029","volume":"8","author":"A.C. Yao","year":"1979","unstructured":"Yao, A.C.: The complexity of pattern matching for a random string. SIAM J. Comput.\u00a08(3), 368\u2013387 (1979)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"4_CR34","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1137\/S0097539703435728","volume":"34","author":"Q. Shi","year":"2005","unstructured":"Shi, Q., J\u00e1J\u00e1, J.: Novel Transformation Techniques Using Q-Heaps with Applications to Computational Geometry. SIAM J. Comput.\u00a034(6), 1474\u20131492 (2005)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38233-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T10:09:41Z","timestamp":1746007781000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38233-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642382321","9783642382338"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38233-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}