{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T13:07:18Z","timestamp":1792156038215,"version":"4.4.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540662792","type":"print"},{"value":"9783540484479","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48447-7_19","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T16:42:14Z","timestamp":1194972134000},"page":"181-192","source":"Crossref","is-referenced-by-count":13,"title":["Indexing and Dictionary Matching with One Error (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dmitry","family":"Keselman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gad M.","family":"Landau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Noa","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Rodeh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,7,18]]},"reference":[{"issue":"6","key":"19_CR1","doi-asserted-by":"publisher","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. Comm. ACM, 18(6):333\u2013340, 1975.","journal-title":"Comm. ACM"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"A. Amir and M. Farach. Adaptive dictionary matching. Proc. 32nd IEEE FOCS, pages 760\u2013766, 1991.","DOI":"10.1109\/SFCS.1991.185445"},{"issue":"2","key":"19_CR3","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/S0022-0000(05)80047-9","volume":"49","author":"A. Amir","year":"1994","unstructured":"A. Amir, M. Farach, R. Giancarlo, Z. Galil, and K. Park. Dynamic dictionary matching. Journal of Computer and System Sciences, 49(2):208\u2013222, 1994.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"19_CR4","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1006\/inco.1995.1090","volume":"119","author":"A. Amir","year":"1995","unstructured":"A. Amir, M. Farach, R. M. Idury, J. A. La Poutr\u00e9, and A. A. Sch\u00e4ffer. Improved dynamic dictionary matching. Information and Computation, 119(2):258\u2013282, 1995.","journal-title":"Information and Computation"},{"key":"19_CR5","doi-asserted-by":"publisher","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. ACM, 20:762\u2013772, 1977.","journal-title":"Comm. ACM"},{"key":"19_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/3-540-61258-0_6","volume-title":"Proc. 7th Annual Symposium on Combinatorial Pattern Matching (CPM 96)","author":"G. S. Brodal","year":"1996","unstructured":"G. S. Brodal and L. Gasieniec. Approximate dictionary queries. In Proc. 7th Annual Symposium on Combinatorial Pattern Matching (CPM 96), pages 65\u201374. LNCS 1075, Springer, 1996."},{"key":"19_CR7","doi-asserted-by":"crossref","unstructured":"M. T. Chen and J. Seiferas. Efficient and elegant subword tree construction. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, chapter 12, pages 97\u2013107. NATO ASI Series F: Computer and System Sciences, 1985.","DOI":"10.1007\/978-3-642-82456-2_7"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"M. Farach. Optimal suffix tree construction with large alphabets. Proc. 38th IEEE Symposium on Foundations of Computer Science, pages 137\u2013143, 1997.","DOI":"10.1109\/SFCS.1997.646102"},{"key":"19_CR9","doi-asserted-by":"crossref","unstructured":"P. Ferragina and R. Grossi. Optimal on-line search and sublinear time update in string matching. Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, pages 531\u2013540, 1995.","DOI":"10.1109\/SFCS.1995.492590"},{"key":"19_CR10","unstructured":"M. J. Fischer and M. S. Paterson. String matching and other products. Complexity of Computation, R.M. Karp (editor), SIAM-AMS Proceedings, 7:113\u2013125, 1974."},{"key":"19_CR11","doi-asserted-by":"crossref","unstructured":"D. Greene, M. Parnas, and F. Yao. Multi-index hashing for information retrieval. Proc. 35th Annual Symposium on Foundations of Computer Science, pages 722\u2013731, 1994.","DOI":"10.1109\/SFCS.1994.365720"},{"key":"19_CR12","unstructured":"M. Gu, M. Farach, and R. Beigel. An efficient algorithm for dynamic text indexing. Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 697\u2013704, 1994."},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"R. M. Idury and A. A Sch\u00e4ffer. Dynamic dictionary matching with failure functions. Proc. 3rd Annual Symposium on Combinatorial Pattern Matching, pages 273\u2013284, 1992.","DOI":"10.1007\/3-540-56024-6_22"},{"key":"19_CR14","first-page":"125","volume":"4","author":"R. Karp","year":"1972","unstructured":"R. Karp, R. Miller, and A. Rosenberg. Rapid identification of repeated patterns in strings, arrays and trees. Symposium on the Theory of Computing, 4:125\u2013136, 1972.","journal-title":"Symposium on the Theory of Computing"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"R. M. Karp and M. O. Rabin. Efficient randomized pattern-matching algorithms. IBM Journal of Res. and Dev., pages 249\u2013260, 1987.","DOI":"10.1147\/rd.312.0249"},{"key":"19_CR16","doi-asserted-by":"crossref","unstructured":"J. M. Kleinberg. Two algorithms for nearest-neighbor searchin high dimensions. Proc. 29th ACM STOC, pages 599\u2013608, 1997.","DOI":"10.1145\/258533.258653"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"323","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. Computing, 6:323\u2013350, 1977.","journal-title":"SIAM J. Computing"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. Proc. 30th ACM STOC, 1998. to appear.","DOI":"10.1145\/276698.276877"},{"key":"19_CR19","first-page":"707","volume":"10","author":"V. I. Levenshtein","year":"1966","unstructured":"V. I. Levenshtein. Binary codes capable of correcting, deletions, insertions and reversals. Soviet Phys. Dokl., 10:707\u2013710, 1966.","journal-title":"Soviet Phys. Dokl."},{"key":"19_CR20","doi-asserted-by":"publisher","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. Journal of the ACM, 23:262\u2013272, 1976.","journal-title":"Journal of the ACM"},{"key":"19_CR21","volume-title":"Perceptrons","author":"M. Minsky","year":"1969","unstructured":"M. Minsky and S. Papert. Perceptrons. MIT Press, Cambridge, Mass., 1969."},{"key":"19_CR22","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0196-6774(88)90041-7","volume":"9","author":"M. H. Overmars","year":"1988","unstructured":"M. H. Overmars. Efficient data structures for range searching on a grid. J. of Algorithms, 9:254\u2013275, 1988.","journal-title":"J. of Algorithms"},{"key":"19_CR23","doi-asserted-by":"crossref","unstructured":"S. C. Sahinalp and U. Vishkin. Efficient approximate and dynamic matching of patterns using a labeling paradigm. Proc. 37th FOCS, pages 320\u2013328, 1996.","DOI":"10.1109\/SFCS.1996.548491"},{"key":"19_CR24","doi-asserted-by":"crossref","unstructured":"P. Weiner. Linear pattern matching algorithm. Proc. 14 IEEE Symposium on Switching and Automata Theory, pages 1\u201311, 1973.","DOI":"10.1109\/SWAT.1973.13"},{"issue":"1","key":"19_CR25","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1006\/jagm.1997.0875","volume":"25","author":"A. C.-C. Yao","year":"1997","unstructured":"A. C.-C. Yao and F. F. Yao. Dictionary lookup with one error. J. of Algorithms, 25(1):194\u2013202, 1997.","journal-title":"J. of Algorithms"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48447-7_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T06:54:57Z","timestamp":1556952897000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48447-7_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540662792","9783540484479"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/3-540-48447-7_19","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[1999]]}}}