{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:30:04Z","timestamp":1787502604104,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540580942","type":"print"},{"value":"9783540484509","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58094-8_17","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:11:52Z","timestamp":1330251112000},"page":"184-197","source":"Crossref","is-referenced-by-count":2,"title":["Dictionary-matching on unbounded alphabets: Uniform length dictionaries"],"prefix":"10.1007","author":[{"given":"Dany","family":"Breslauer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"17_CR1","first-page":"257","volume-title":"Handbook of Theoretical Computer Science","author":"A.V. Aho","year":"1990","unstructured":"A.V. Aho. Algorithms for Finding Patterns in Strings. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, pages 257\u2013300, Elsevier Science Publishers B. V., Amsterdam, the Netherlands. 1990."},{"issue":"6","key":"17_CR2","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: An aid to bibliographic search. Comm. of the ACM. 18(6):333\u2013340, 1975.","journal-title":"Comm. of the ACM."},{"key":"17_CR3","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1971","unstructured":"A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley. Reading. MA. 1971."},{"key":"17_CR4","unstructured":"A. Amir and G. Benson. Two-dimensional periodicity and its applications. In Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms, pages 440\u2013452, 1992."},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"A. Amir, G. Benson, and M. Farach. Alphabet-Independent. Two-Dimensional Matching. In Proc. 24th ACM Symp. on Theory of Computing, pages 59\u201368, 1992.","DOI":"10.1145\/129712.129719"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"A. Amir and M. Farach. Adaptive dictionary matching. In Proc. 32th IEEE Symp. on Foundations of Computer Science. pages 760\u2013766, 1991.","DOI":"10.1109\/SFCS.1991.185445"},{"key":"17_CR7","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0020-0190(92)90206-B","volume":"44","author":"A. Amir","year":"1992","unstructured":"A. Amir and M. Farach. Two-dimensional dictionary matching. Inform. Process. Lett., 44:223\u2013239, 1992.","journal-title":"Inform. Process. Lett."},{"key":"17_CR8","unstructured":"A. Amir, M. Farach, Z. Galil, R. Giancarlo, and K. Park. Dynamic Dictionary Matching. Manuscript, 1992."},{"key":"17_CR9","unstructured":"A. Amir, M. Farach, R.M. Idury, J.A. La Poutr\u00e9, and A.A. Sch\u00e4ffer. Improved Dynamic Dictionary-Matching. In Proc. 4nd ACM-SIAM Symp. on Discrete Algorithms, pages 392\u2013401, 1993."},{"key":"17_CR10","first-page":"262","volume-title":"number 644 in Lecture Notes in Computer Science","author":"A. Amir","year":"1992","unstructured":"A. Amir, M. Farach, and Y. Matias. Efficient Randomized Dictionary-Matching Algorithms. In Proc. 3rd Symp. on Combinatorial Pattern Matching, number 644 in Lecture Notes in Computer Science, pages 262\u2013275. Springer-Verlag, Berlin, Germany, 1992."},{"key":"17_CR11","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 with applications. Algorithmica, 3:347\u2013365. 1988.","journal-title":"Algorithmica"},{"key":"17_CR12","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0020-0190(93)90250-D","volume":"45","author":"R. Baeze-Yates","year":"1993","unstructured":"R. Baeze-Yates and M. R\u00e9gnier. Fast two-dimensional pattern matching. Inform. Process. Lett., 45:51\u201357, 1993.","journal-title":"Inform. Process. Lett."},{"issue":"4","key":"17_CR13","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1137\/0207043","volume":"7","author":"T.P. Baker","year":"1978","unstructured":"T.P. Baker. A Technique for Extending Rapid Exact-Match String Matching to Arrays of More than One Dimension. SIAM J. Comput., 7(4):533\u2013541, 1978.","journal-title":"SIAM J. Comput."},{"key":"17_CR14","unstructured":"G.E. Benson. Two-Dimensional Periodicity and Matching Algorithms. PhD thesis, Dept. of Computer Science. University of Maryland. 1992."},{"issue":"5","key":"17_CR15","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/0020-0190(77)90017-5","volume":"6","author":"R.S. Bird","year":"1977","unstructured":"R.S. Bird. Two Dimensional Pattern Matching. Inform. Process. Lett., 6(5): 168\u2013170, 1977.","journal-title":"Inform. Process. Lett."},{"key":"17_CR16","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R.S. Boyer","year":"1977","unstructured":"R.S. Boyer and J.S. Moore. A fast string searching algorithm. Comm. of the ACM, 20:762\u2013772, 1977.","journal-title":"Comm. of the ACM"},{"key":"17_CR17","series-title":"volume 12 of NATO ASI Series F","first-page":"97","volume-title":"Combinatorial Algorithms on Words","author":"M.T. Chen","year":"1984","unstructured":"M.T. Chen and J. Seiferas. Efficient and elegant subword-tree construction. In A. Apostolico and Z. Galil. editors. Combinatorial Algorithms on Words, volume 12 of NATO ASI Series F, pages 97\u2013107. Springer-Verlag, Berlin. Germany, 1984."},{"key":"17_CR18","first-page":"118","volume-title":"Lecture Notes in Computer Science","author":"B. Commentz-Walter","year":"1979","unstructured":"B. Commentz-Walter. A string matching algorithm fast on the average. In Proc. 6th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science. pages 118\u2013132. Springer-Verlag. Berlin, Germany, 1979."},{"key":"17_CR19","volume-title":"A string matching algorithm last on the average. Technical Report 79.09.007","author":"B. Commentz-Walter","year":"1979","unstructured":"B. Commentz-Walter. A string matching algorithm last on the average. Technical Report 79.09.007, IBM Wissenschaftliches Zentrum. Heidelberg. Germany, 1979."},{"key":"17_CR20","volume-title":"Fast Practical Multi-Pattern Matching. Technical Report. 93-3","author":"M. Crochemore","year":"1993","unstructured":"M. Crochemore, A. Czumaj, L. Gasieniec, S. Jarominek, T. Lecroq, W. Plandowski, and W. Rytter. Fast Practical Multi-Pattern Matching. Technical Report. 93-3, Institut Gaspard Monge, Universit\u00e9 de Marne la Vall\u00e9e. Marne la Vall\u00e9e, France, 1993."},{"key":"17_CR21","volume-title":"number 623 in Lecture Notes in Computer Science","author":"M. Dietzfelbinger","year":"1992","unstructured":"M. Dietzfelbinger, J. Gil, Y. Matias, and N. Pippenger. Polynomial Hash Functions Are Reliable. In Proc. 19th International Colloquium on Automata, Languages, and Programming, number 623 in Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany, 1992."},{"issue":"3","key":"17_CR22","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. Komlos, and E. Szemeredi. Storing a sparse table with O(1) worst case access time. J. Assoc. Comput. Mach., 31(3):538\u2013544, 1984.","journal-title":"J. Assoc. Comput. Mach."},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"Z. Galil and K. Park. Truly Alphabet-Independent Two-Dimensional Pattern Matching. In Proc. 33th IEEE Symp. on Foundations of Computer Science, pages 247\u2013256, 1992.","DOI":"10.1109\/SFCS.1992.267767"},{"key":"17_CR24","first-page":"276","volume-title":"number 644 in Lecture Notes in Computer Science","author":"R.M. Idury","year":"1992","unstructured":"R.M. Idury and A.A. Sch\u00e4ffer. Dynamic Dictionary-Matching with Failure Functions. In Proc. 3rd Symp. on Combinatorial Pattern Matching. number 644 in Lecture Notes in Computer Science, pages 276\u2013287. Springer-Verlag, Berlin, Germany, 1992."},{"issue":"2","key":"17_CR25","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. Res. Develop., 31(2):249\u2013260. 1987.","journal-title":"IBM J. Res. Develop."},{"key":"17_CR26","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"D.E. Knuth, J.H. Morris, and V.R. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6:322\u2013350, 1977.","journal-title":"SIAM J. Comput."},{"key":"17_CR27","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"E.M. McCreight. A space economical suffix tree construction algorithm. J. Assoc. Comput. Mach., 23:262\u2013272, 1976.","journal-title":"J. Assoc. Comput. Mach."},{"key":"17_CR28","first-page":"215","volume-title":"number 684 in Lecture Notes in Computer Science","author":"M. R\u00e9gnier","year":"1993","unstructured":"M. R\u00e9gnier and L. Rostami. A Unifying Look at d-dimensional Periodicities and Space Coverings. In Proc. 4rd Symp. on Combinatorial Pattern Matching, number 684 in Lecture Notes in Computer Science. pages 215\u2013227. Berlin, Germany, 1993. Springer-Verlag."},{"key":"17_CR29","volume-title":"Data Structures and Network Algorithms","author":"R.E. Tarjan","year":"1985","unstructured":"R.E. Tarjan. Data Structures and Network Algorithms. SIAM, Philadelphia, PA., 1985."},{"key":"17_CR30","doi-asserted-by":"crossref","unstructured":"P. Weiner. Linear pattern matching algorithms. In Proc. 14th Symposium on Switching and Automata Theory, pages 1\u201311, 1973.","DOI":"10.1109\/SWAT.1973.13"},{"issue":"9","key":"17_CR31","doi-asserted-by":"crossref","first-page":"1110","DOI":"10.1145\/66451.66459","volume":"32","author":"R.F. Zhu","year":"1989","unstructured":"R.F. Zhu and T. Takaoka. A Technique for Two-Dimensional Pattern Matching. Comm. of the ACM. 32(9):1110\u20131120, 1989.","journal-title":"Comm. of the ACM."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58094-8_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:10:52Z","timestamp":1619557852000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58094-8_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540580942","9783540484509"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-58094-8_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994]]}}}