{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T17:05:07Z","timestamp":1770483907943,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642312649","type":"print"},{"value":"9783642312656","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31265-6_7","type":"book-chapter","created":{"date-parts":[[2012,6,12]],"date-time":"2012-06-12T03:28:23Z","timestamp":1339471703000},"page":"83-96","source":"Crossref","is-referenced-by-count":2,"title":["Constant-Time Word-Size String Matching"],"prefix":"10.1007","author":[{"given":"Dany","family":"Breslauer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leszek","family":"G\u0105sieniec","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"7_CR1","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1002\/spe.4380190305","volume":"19","author":"R.A. Baeza-Yates","year":"1989","unstructured":"Baeza-Yates, R.A.: Improved string searching. Softw. Pract. Exper.\u00a019(3), 257\u2013271 (1989)","journal-title":"Softw. Pract. Exper."},{"key":"7_CR2","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":"7_CR3","unstructured":"Ben-Kiki, O., Bille, P., Breslauer, D., G\u0105sieniec, L., Grossi, R., Weimann, O.: Optimal Packed String Matching. In: Proc. FSTTCS. LIPIcs, vol.\u00a013, pp. 423\u2013432. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2011)"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1007\/978-3-540-76336-9_14","volume-title":"Implementation and Application of Automata","author":"S.T. Klein","year":"2007","unstructured":"Klein, S.T., Kopel Ben-Nissan, M.: Accelerating Boyer Moore Searches on Binary Texts. In: Holub, J., \u017d\u010f\u00e1rek, J. (eds.) CIAA 2007. LNCS, vol.\u00a04783, pp. 130\u2013143. Springer, Heidelberg (2007)"},{"issue":"1","key":"7_CR5","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.jda.2010.09.003","volume":"9","author":"P. Bille","year":"2011","unstructured":"Bille, P.: Fast searching in packed strings. J. Discrete Algorithms\u00a09(1), 49\u201356 (2011)","journal-title":"J. Discrete Algorithms"},{"key":"7_CR6","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R. Boyer","year":"1977","unstructured":"Boyer, R., Moore, J.: A fast string searching algorithm. Comm. of the ACM\u00a020, 762\u2013772 (1977)","journal-title":"Comm. of the ACM"},{"issue":"2","key":"7_CR7","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0020-0190(97)00032-X","volume":"62","author":"D. Breslauer","year":"1997","unstructured":"Breslauer, D., Czumaj, A., Dubhashi, D.P., Meyer auf der Heide, F.: Comparison Model Lower Bounds to the Parallel-Random-Access-Machine. Inf. Process. Lett.\u00a062(2), 103\u2013110 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"7_CR8","doi-asserted-by":"publisher","first-page":"1051","DOI":"10.1137\/0219072","volume":"19","author":"D. Breslauer","year":"1990","unstructured":"Breslauer, D., Galil, Z.: An optimal O(loglogn) time parallel string matching algorithm. SIAM J. Comput.\u00a019(6), 1051\u20131058 (1990)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"7_CR9","doi-asserted-by":"publisher","first-page":"856","DOI":"10.1137\/0221050","volume":"21","author":"D. Breslauer","year":"1992","unstructured":"Breslauer, D., Galil, Z.: A Lower Bound for Parallel String Matching. SIAM J. Comput.\u00a021(5), 856\u2013862 (1992)","journal-title":"SIAM J. Comput."},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Cole, R., Crochemore, M., Galil, Z., G\u0105sieniec, L., Hariharan, R., Muthukrishnan, S., Park, K., Rytter, W.: Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. In: Proc. FOCS, pp. 248\u2013258 (1993)","DOI":"10.1109\/SFCS.1993.366862"},{"issue":"4","key":"7_CR11","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1137\/S009753979528007X","volume":"26","author":"M. Crochemore","year":"1997","unstructured":"Crochemore, M., Galil, Z., G\u0105sieniec, L., Park, K., Rytter, W.: Constant-Time Randomized Parallel String Matching. SIAM J. Comput.\u00a026(4), 950\u2013960 (1997)","journal-title":"SIAM J. Comput."},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Galil, Z., G\u0105sieniec, L., Park, K., Plandowski, W.: Work-time-optimal parallel algorithms for string problems. In: Proc. STOC, pp. 713\u2013722. ACM (1995)","DOI":"10.1145\/225058.225289"},{"key":"7_CR13","unstructured":"Faro, S., Lecroq, T.: Efficient pattern matching on binary strings. In: Proc. SOFSEM (2009)"},{"key":"7_CR14","unstructured":"Fich, F.E.: Constant Time Operations for Words of Length w. Technical report, University of Toronto (1999), http:\/\/www.cs.toronto.edu\/~faith\/algs.ps"},{"key":"7_CR15","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":"4","key":"7_CR16","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/S0020-0190(03)00296-5","volume":"87","author":"K. Fredriksson","year":"2003","unstructured":"Fredriksson, K.: Shift-or string matching with super-alphabets. IPL\u00a087(4), 201\u2013204 (2003)","journal-title":"IPL"},{"issue":"1","key":"7_CR17","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M.L. Furst","year":"1984","unstructured":"Furst, M.L., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory\u00a017(1), 13\u201327 (1984)","journal-title":"Mathematical Systems Theory"},{"key":"7_CR18","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/S0019-9958(85)80031-0","volume":"67","author":"Z. Galil","year":"1985","unstructured":"Galil, Z.: Optimal parallel algorithms for string matching. Inform. and Control\u00a067, 144\u2013157 (1985)","journal-title":"Inform. and Control"},{"issue":"4","key":"7_CR19","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1145\/210332.210341","volume":"42","author":"Z. Galil","year":"1995","unstructured":"Galil, Z.: A Constant-Time Optimal Parallel String-Matching Algorithm. J. ACM\u00a042(4), 908\u2013918 (1995)","journal-title":"J. ACM"},{"key":"7_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/3-540-60044-2_36","volume-title":"Combinatorial Pattern Matching","author":"L. G\u0105sieniec","year":"1995","unstructured":"G\u0105sieniec, L., Plandowski, W., Rytter, W.: Constant-space String Matching with Smaller Number of Comparisons: Sequential Sampling. In: Galil, Z., Ukkonen, E. (eds.) CPM 1995. LNCS, vol.\u00a0937, pp. 78\u201389. Springer, Heidelberg (1995)"},{"issue":"2","key":"7_CR21","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1006\/jagm.1994.1014","volume":"16","author":"T. Goldberg","year":"1994","unstructured":"Goldberg, T., Zwick, U.: Faster parallel string matching via larger deterministic samples. J. Algorithms\u00a016(2), 295\u2013308 (1994)","journal-title":"J. Algorithms"},{"key":"7_CR22","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1137\/0206024","volume":"6","author":"D. Knuth","year":"1977","unstructured":"Knuth, D., Morris, J., Pratt, V.: Fast pattern matching in strings. SIAM J. Comput.\u00a06, 322\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"7_CR23","unstructured":"Knuth, D.E.: Combinatorial Algorithms. The Art of Computer Programming, vol.\u00a04A. Addison-Wesley Professional (January 2011)"},{"key":"7_CR24","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":"7_CR25","doi-asserted-by":"publisher","first-page":"851","DOI":"10.1002\/(SICI)1097-024X(199707)27:7<851::AID-SPE108>3.0.CO;2-D","volume":"27","author":"J. Tarhio","year":"1997","unstructured":"Tarhio, J., Peltola, H.: String matching in the DNA alphabet. Software Practice Experience\u00a027, 851\u2013861 (1997)","journal-title":"Software Practice Experience"},{"key":"7_CR26","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/S0019-9958(85)80028-0","volume":"67","author":"U. Vishkin","year":"1985","unstructured":"Vishkin, U.: Optimal parallel pattern matching in strings. Inform. and Control\u00a067, 91\u2013113 (1985)","journal-title":"Inform. and Control"},{"issue":"1","key":"7_CR27","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1137\/0220002","volume":"20","author":"U. Vishkin","year":"1990","unstructured":"Vishkin, U.: Deterministic sampling - A new technique for fast pattern matching. SIAM J. Comput.\u00a020(1), 22\u201340 (1990)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31265-6_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T22:43:24Z","timestamp":1743374604000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31265-6_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642312649","9783642312656"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31265-6_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}