{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T17:52:40Z","timestamp":1793123560939,"version":"4.5.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540560241","type":"print"},{"value":"9783540473572","type":"electronic"}],"license":[{"start":{"date-parts":[[1992,1,1]],"date-time":"1992-01-01T00:00:00Z","timestamp":694224000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-56024-6_21","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:53:59Z","timestamp":1330253639000},"page":"262-275","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Efficient randomized dictionary matching algorithms"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Farach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yossi","family":"Matias","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"issue":"6","key":"21_CR1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A. V. Aho","year":"1975","unstructured":"A. V. Aho and M. J. Corasick. Efficient string matching. Commun. ACM, 18(6):333\u2013340, 1975.","journal-title":"Commun. ACM"},{"key":"21_CR2","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman. Data Structures and Algorithms. Addison-Wesley Publishing Company, 1983."},{"key":"21_CR3","unstructured":"A. Amir and M. Farach. Adaptive dictionary matching. FOCS '91, 1991."},{"key":"21_CR4","unstructured":"A. Amir, M. Farach, R. Giancarlo, Z. Galil, and K. Park. Dynamic dictionary matching. Manuscript, 1991."},{"key":"21_CR5","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/BF01762122","volume":"3","author":"A. Apostolico","year":"1988","unstructured":"A. Apostolico, C. Iliopoulos, G. M. Landau, B. Schieber, and U. Vishkin. Parallel construction of a suffix tree. Algorithmica, 3:347\u2013365, 1988.","journal-title":"Algorithmica"},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"H. Bast and T. Hagerup. Fast and reliable parallel hashing. In SPAA '91, pages 50\u201361, July 1991.","DOI":"10.1145\/113379.113384"},{"key":"21_CR7","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R. Boyer","year":"1977","unstructured":"R. Boyer and J. Moore. A fast string searching algorithm. Commun. ACM, 20:762\u2013772, 1977.","journal-title":"Commun. ACM"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger, J. Gil, Y. Matias, and N. Pippenger. Polynomial hash functions are reliable. In ICALP '92, July 1992.","DOI":"10.1007\/3-540-55719-9_77"},{"key":"21_CR9","unstructured":"M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. In FOCS '88, pages 524\u2013531, Oct. 1988. Also, Revised Version: Tech. Report, University of Paderborn, FB 17 Mathematik\/Informatik, 1991."},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. An optimal parallel dictionary. In SPAA '89, pages 360\u2013368, 1989.","DOI":"10.1145\/72935.72974"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"M. Dietzfelbinger and F. Meyer auf der Heide. A new universal class of hash functions and dynamic hahshing in real time. In ICALP '90, pages 6\u201319, 1990.","DOI":"10.1007\/BFb0032018"},{"issue":"3","key":"21_CR12","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M. L. Fredman","year":"1984","unstructured":"M. L. Fredman, J. Koml\u00f3s, and E. Szemer\u00e9di. Storing a sparse table with O(1) worst case access time. J. ACM, 31(3):538\u2013544, July 1984.","journal-title":"J. ACM"},{"key":"21_CR13","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/0885-064X(88)90008-8","volume":"4","author":"Z. Galil","year":"1988","unstructured":"Z. Galil and R. Giancarlo. Data structures and algorithms for approximate string matching. J. of Complexity, 4:33\u201372, 1988.","journal-title":"J. of Complexity"},{"key":"21_CR14","unstructured":"J. Gil and Y. Matias. Fast hashing on a PRAM\u2014designing by expectation. In SODA '91, pages 271\u2013280, Jan. 1991."},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"J. Gil, Y. Matias, and U. Vishkin. Towards a theory of nearly constant time parallel algorithms. In FOCS '91, pages 698\u2013710, Oct. 1991.","DOI":"10.1109\/SFCS.1991.185438"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"R. Indury and A. Schaeffer. Dynamic dictionary matching with failure functions. In Combinatorial Pattern Matching, 1992.","DOI":"10.1007\/3-540-56024-6_22"},{"key":"21_CR17","first-page":"185","volume":"70","author":"C. Jordan","year":"1869","unstructured":"C. Jordan. Sur le assemblages des lignes. J. Reine und Ang. Math., 70:185\u2013190, 1869.","journal-title":"J. Reine und Ang. Math."},{"key":"21_CR18","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R. M. Karp","year":"1987","unstructured":"R. M. Karp and M. O. Rabin. Efficient randomized pattern-matching algorithms. IBM J. of Research and Development, 31:249\u2013260, 1987.","journal-title":"IBM J. of Research and Development"},{"key":"21_CR19","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D. Knuth","year":"1977","unstructured":"D. Knuth, J. Morris, and V. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6:323\u2013350, 1977.","journal-title":"SIAM J. Comput."},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Y. Matias and U. Vishkin. Converting high probability into nearly-constant time\u2014 with applications to parallel hashing. In STOC '91, pages 307\u2013316, 1991. Also in UMIACS-TR-91-65, Inst. for Advanced Computer Studies, Univ. of Maryland, April 1991.","DOI":"10.1145\/103418.103453"},{"issue":"4","key":"21_CR21","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1016\/0196-6774(91)90034-V","volume":"12","author":"Y. Matias","year":"1991","unstructured":"Y. Matias and U. Vishkin. On parallel hashing and integer sorting. J. of Alg., 12(4):573\u2013606, 1991.","journal-title":"J. of Alg."},{"key":"21_CR22","doi-asserted-by":"crossref","first-page":"852","DOI":"10.1145\/2157.322410","volume":"28","author":"N. Megiddo","year":"1983","unstructured":"N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. J. ACM, 28:852\u2013865, 1983.","journal-title":"J. ACM"},{"key":"21_CR23","volume-title":"Multi-dimensional Searching and Computational Geometry","author":"K. Mehlhorn","year":"1984","unstructured":"K. Mehlhorn. Multi-dimensional Searching and Computational Geometry. Springer-Verlag, Berlin Heidelberg, 1984."},{"key":"21_CR24","doi-asserted-by":"crossref","unstructured":"M. Naor. String matching with preprocessing of text and pattern. In ICALP '91, pages 739\u2013750, 1991.","DOI":"10.1007\/3-540-54233-7_179"},{"key":"21_CR25","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R. E. Tarjan","year":"1975","unstructured":"R. E. Tarjan. Efficiency of a good but not linear set union algorithm. J. ACM, 22:215\u2013225, 1975.","journal-title":"J. ACM"},{"key":"21_CR26","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","volume":"14","author":"R. E. Tarjan","year":"1985","unstructured":"R. E. Tarjan and U. Vishkin. Finding biconnected components and computing tree functions in logarithmic parallel time. SIAM J. Comput., 14:862\u2013874, 1985.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56024-6_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:45:57Z","timestamp":1742593557000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56024-6_21"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540560241","9783540473572"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-56024-6_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992]]},"assertion":[{"value":"4 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}