{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T05:30:16Z","timestamp":1737437416780,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540755296"},{"type":"electronic","value":"9783540755302"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-75530-2_4","type":"book-chapter","created":{"date-parts":[[2007,9,19]],"date-time":"2007-09-19T14:26:50Z","timestamp":1190212010000},"page":"39-49","source":"Crossref","is-referenced-by-count":9,"title":["Efficient Computations of \u21131 and \u2113\u2009\u221e\u2009 Rearrangement Distances"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yonatan","family":"Aumann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Piotr","family":"Indyk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avivit","family":"Levy","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"4_CR1","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0196-6774(03)00097-X","volume":"50","author":"A. Amir","year":"2004","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with k mismatches. J. Algorithms\u00a050(2), 257\u2013275 (2004)","journal-title":"J. Algorithms"},{"issue":"4","key":"4_CR2","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":"4_CR3","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"},{"issue":"6","key":"4_CR4","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."},{"issue":"2","key":"4_CR5","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":"4_CR6","first-page":"463","volume-title":"Proc. 9th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"R. Cole","year":"1998","unstructured":"Cole, R., Hariharan, R.: Approximate string matching: A faster simpler algorithm. In: Proc. 9th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 463\u2013472. ACM Press, New York (1998)"},{"key":"4_CR7","first-page":"707","volume":"10","author":"V.I. Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting, deletions, insertions and reversals. Soviet Phys. Dokl.\u00a010, 707\u2013710 (1966)","journal-title":"Soviet Phys. Dokl."},{"key":"4_CR8","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/1007352.1007374","volume-title":"STOC 2004: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing","author":"R. Cole","year":"2004","unstructured":"Cole, R., Gottlieb, L., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: STOC 2004: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pp. 91\u2013100. ACM Press, New York (2004)"},{"key":"4_CR9","first-page":"531","volume-title":"Proc. 7th ACM-SIAM Symposium on Discrete Algorithms","author":"P. Ferragina","year":"1995","unstructured":"Ferragina, P., Grossi, R.: Fast incremental text editing. In: Proc. 7th ACM-SIAM Symposium on Discrete Algorithms, pp. 531\u2013540. ACM Press, New York (1995)"},{"key":"4_CR10","first-page":"697","volume-title":"Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"M. Gu","year":"1994","unstructured":"Gu, M., Farach, M., Beigel, R.: An efficient algorithm for dynamic text indexing. In: Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 697\u2013704. ACM Press, New York (1994)"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Sahinalp, S.C., Vishkin, U.: Efficient approximate and dynamic matching of patterns using a labeling paradigm. In: Proc. 37th FOCS, pp. 320\u2013328 (1996)","DOI":"10.1109\/SFCS.1996.548491"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Lowrance, R., Wagner, R.A.: An extension of the string-to-string correction problem. J. of the ACM, 177\u2013183 (1975)","DOI":"10.1145\/321879.321880"},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/3-540-61258-0_14","volume-title":"Combinatorial Pattern Matching","author":"P. Berman","year":"1996","unstructured":"Berman, P., Hannenhalli, S.: Fast sorting by reversal. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol.\u00a01075, pp. 168\u2013185. Springer, Heidelberg (1996)"},{"key":"4_CR14","first-page":"75","volume-title":"RECOMB 1997","author":"A. Carpara","year":"1997","unstructured":"Carpara, A.: Sorting by reversals is difficult. In: RECOMB 1997, pp. 75\u201383. ACM Press, New York (1997)"},{"key":"4_CR15","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V. Bafna","year":"1998","unstructured":"Bafna, V., Pevzner, P.: Sorting by transpositions. SIAM J. on Discrete Mathematics\u00a011, 221\u2013240 (1998)","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"4_CR16","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(96)00155-X","volume":"60","author":"D.A. Christie","year":"1996","unstructured":"Christie, D.A.: Sorting by block-interchanges. Information Processing Letters\u00a060, 165\u2013169 (1996)","journal-title":"Information Processing Letters"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Amir, A., Aumann, Y., Benson, G., Levy, A., Lipsky, O., Porat, E., Skiena, S., Vishne, U.: Pattern matching with address errors: Rearrangement distances. In: Proc. 17th SODA, pp. 1221\u20131229 (2006)","DOI":"10.1145\/1109557.1109692"},{"key":"4_CR18","unstructured":"Amir, A., Aumann, Y., Kapah, O., Levy, A., Porat, E.: Approximate string matching with address bit errors Manuscript"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","volume-title":"ESA","author":"A. Amir","year":"2007","unstructured":"Amir, A., Hartman, T., Kapah, O., Levy, A., Porat, E.: On the cost of interchange rearrangement in strings. In: Arge, L., Welzl, E. (eds.) ESA. LNCS, vol.\u00a04698, Springer, Heidelberg (2007)"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Zolotarev, V.: One-dimensional stable distributions. Translations of Mathematical Monographs 65 (1986)","DOI":"10.1090\/mmono\/065"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Stable distributions, pseudorandom generators, embeddings and data stream computation. In: FOCS, pp. 189\u2013197 (2000)","DOI":"10.1109\/SFCS.2000.892082"},{"key":"4_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"782","DOI":"10.1007\/978-3-540-27836-8_66","volume-title":"Automata, Languages and Programming","author":"P. Indyk","year":"2004","unstructured":"Indyk, P., Lewenstein, M., Lipsky, O., Porat, E.: Closest pair problems in very high dimensions. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 782\u2013792. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75530-2_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T03:09:25Z","timestamp":1737428965000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75530-2_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540755296","9783540755302"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75530-2_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}