{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T05:40:20Z","timestamp":1775281220190,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540262015","type":"print"},{"value":"9783540315629","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11496656_9","type":"book-chapter","created":{"date-parts":[[2010,9,25]],"date-time":"2010-09-25T15:17:26Z","timestamp":1285427846000},"page":"91-103","source":"Crossref","is-referenced-by-count":16,"title":["Approximate Matching in the L 1 Metric"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ohad","family":"Lipsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julia","family":"Umanski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"9_CR1","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"K. Abrahamson","year":"1987","unstructured":"Abrahamson, K.: Generalized string matching. SIAM J. Comp.\u00a016(6), 1039\u20131051 (1987)","journal-title":"SIAM J. Comp."},{"key":"9_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1007\/3-540-45061-0_72","volume-title":"Automata, Languages and Programming","author":"A. Amir","year":"2003","unstructured":"Amir, A., Aumann, A., Cole, R., Lewenstein, M., Porat, E.: Function matching: Algorithms, applications, and a lower bound. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 929\u2013942. Springer, Heidelberg (2003)"},{"issue":"1","key":"9_CR3","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0890-5401(02)00035-4","volume":"181","author":"A. Amir","year":"2003","unstructured":"Amir, A., Cole, R., Hariharan, R., Lewenstein, M., Porat, E.: Overlap matching. Information and Computation\u00a0181(1), 57\u201374 (2003)","journal-title":"Information and Computation"},{"key":"9_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-540-30140-0_4","volume-title":"Algorithms \u2013 ESA 2004","author":"A. Amir","year":"2004","unstructured":"Amir, A., Eisenberg, E., Porat, E.: Swap and mismatch edit distance. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol.\u00a03221, pp. 16\u201327. Springer, Heidelberg (2004)"},{"issue":"1","key":"9_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1995.1047","volume":"118","author":"A. Amir","year":"1995","unstructured":"Amir, A., Farach, M.: Efficient 2-dimensional approximate matching of halfrectangular figures. Information and Computation\u00a0118(1), 1\u201311 (1995)","journal-title":"Information and Computation"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. J. Algorithms (2004)","DOI":"10.1016\/S0196-6774(03)00097-X"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Berkman, O., Breslauer, D., Galil, Z., Schieber, B., Vishkin, U.: Highly parallelizable problems. In: Proc. 21st ACM Symposium on Theory of Computation, pp. 309\u2013319 (1989)","DOI":"10.1145\/73007.73036"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Cole, R., Hariharan, R.: Verifying candidate matches in sparse and wildcard matching. In: Proc. 34st Annual Symposium on the Theory of Computing (STOC), pp. 592\u2013601 (2002)","DOI":"10.1145\/509907.509992"},{"key":"9_CR9","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. In: Proc. 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 667\u2013676. Society for Industrial and Applied Mathematics (2002)"},{"key":"9_CR10","unstructured":"Fischer, M.J., Paterson, M.S.: String matching and other products. In: Karp, R.M. (ed.) Complexity of Computation. SIAM-AMS Proceedings, vol.\u00a07, pp. 113\u2013125 (1974)"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Galil, Z.: Open problems in stringology. In: Galil, Z., Apostolico, A. (eds.) Combinatorial Algorithms on Words. NATO ASI Series F, vol.\u00a012, pp. 1\u20138 (1985)","DOI":"10.1007\/978-3-642-82456-2_1"},{"issue":"4","key":"9_CR12","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/8307.8309","volume":"17","author":"Z. Galil","year":"1986","unstructured":"Galil, Z., Giancarlo, R.: Improved string matching with k mismatches. SIGACT News\u00a017(4), 52\u201354 (1986)","journal-title":"SIGACT News"},{"key":"9_CR13","first-page":"338","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestor. Computer and System Science\u00a013, 338\u2013355 (1984)","journal-title":"Computer and System Science"},{"issue":"2","key":"9_CR14","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0020-0190(93)90177-B","volume":"48","author":"H. Karloff","year":"1993","unstructured":"Karloff, H.: Fast algorithms for approximately counting mismatches. Information Processing Letters\u00a048(2), 53\u201360 (1993)","journal-title":"Information Processing Letters"},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","volume":"43","author":"G.M. Landau","year":"1986","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching with k mismatches. Theoretical Computer Science\u00a043, 239\u2013249 (1986)","journal-title":"Theoretical Computer Science"},{"key":"9_CR16","unstructured":"Lipsky, O.: Efficient distance computations. Master\u2019s thesis, Bar-Ilan University, Department of Computer Science, Ramat-Gan 52900, ISRAEL (2003)"},{"issue":"1","key":"9_CR17","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0304-4076(01)00125-7","volume":"107","author":"E. Maasoumi","year":"2002","unstructured":"Maasoumi, E., Racine, J.: Entropy and predictability of stock market returns. Journal of Econometrics\u00a0107(1), 291\u2013312 (2002), available at \n                  \n                    http:\/\/ideas.repec.org\/a\/eee\/econom\/v107y2002i1-2p291-312.html","journal-title":"Journal of Econometrics"},{"key":"9_CR18","doi-asserted-by":"publisher","first-page":"1062","DOI":"10.1785\/0119990152","volume":"90","author":"L. Malagnini","year":"2000","unstructured":"Malagnini, L., Herman, R.B., Di Bona, M.: Ground motion scaling in the apennines (italy). Bull. Seism. Soc. Am.\u00a090, 1062\u20131081 (2000)","journal-title":"Bull. Seism. Soc. Am."},{"key":"9_CR19","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. of the ACM\u00a023, 262\u2013272 (1976)","journal-title":"J. of the ACM"},{"key":"9_CR20","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1126\/science.270.5235.394","volume":"270","author":"M.V. Olson","year":"1995","unstructured":"Olson, M.V.: A time to sequence. Science\u00a0270, 394\u2013396 (1995)","journal-title":"Science"},{"key":"9_CR21","unstructured":"Pentland, A.: Invited talk. In: NSF Institutional Infrastructure Workshop (1992)"},{"key":"9_CR22","unstructured":"Shmulevich, I., Yli-Harja, O., Coyle, E., Povel, D., Lemstrom, K.: Perceptual issues in music pattern recognition \u2014 complexity of rhythm and key finding (April 1999)"},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proc. 14 IEEE Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11496656_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T02:40:18Z","timestamp":1619491218000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11496656_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540262015","9783540315629"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11496656_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}