{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T05:51:53Z","timestamp":1794376313560,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":38,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642124754","type":"print"},{"value":"9783642124761","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-12476-1_1","type":"book-chapter","created":{"date-parts":[[2010,4,8]],"date-time":"2010-04-08T09:46:37Z","timestamp":1270719997000},"page":"1-33","source":"Crossref","is-referenced-by-count":8,"title":["String Rearrangement Metrics: A Survey"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avivit","family":"Levy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"1_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11780441_1","volume-title":"Combinatorial Pattern Matching","author":"A. Amir","year":"2006","unstructured":"Amir, A.: Asynchronous pattern matching. In: Lewenstein, M., Valiente, G. (eds.) CPM 2006. LNCS, vol.\u00a04009, pp. 1\u201310. Springer, Heidelberg (2006) (invited Talk)"},{"key":"1_CR2","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":"1_CR3","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. Journal of Computer and System Sciences\u00a075(6) (2009)","DOI":"10.1016\/j.jcss.2009.03.001"},{"key":"1_CR4","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, Y., 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)"},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-540-75530-2_4","volume-title":"String Processing and Information Retrieval","author":"A. Amir","year":"2007","unstructured":"Amir, A., Aumann, Y., Indyk, P., Levy, A., Porat, E.: Efficient computations of \u21131 and \u2113\u2009\u221e\u2009 rearrangement distances. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol.\u00a04726, pp. 39\u201349. Springer, Heidelberg (2007)"},{"issue":"43","key":"1_CR6","doi-asserted-by":"publisher","first-page":"4382","DOI":"10.1016\/j.tcs.2009.07.019","volume":"410","author":"A. Amir","year":"2009","unstructured":"Amir, A., Aumann, Y., Indyk, P., Levy, A., Porat, E.: Efficient computations of \u21131 and \u2113\u2009\u221e\u2009 rearrangement distances. Theoretical Computer Science\u00a0410(43), 4382\u20134390 (2009)","journal-title":"Theoretical Computer Science"},{"key":"1_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-540-69068-9_13","volume-title":"Combinatorial Pattern Matching","author":"A. Amir","year":"2008","unstructured":"Amir, A., Aumann, Y., Kapah, O., Levy, A., Porat, E.: Approximate string matching with address bit errors. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 118\u2013129. Springer, Heidelberg (2008)"},{"key":"#cr-split#-1_CR8.1","doi-asserted-by":"crossref","unstructured":"Amir, A., Aumann, Y., Kapah, O., Levy, A., Porat, E.: Approximate string matching with address bit errors. Theoretical Computer Science??410(51) (2009);","DOI":"10.1016\/j.tcs.2009.09.010"},{"key":"#cr-split#-1_CR8.2","unstructured":"Special Issue of CPM 2008 Best Papers"},{"issue":"1","key":"1_CR9","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":"1_CR10","unstructured":"Amir, A., Eisenberg, E., Keller, O., Levy, A., Porat, E.: Approximate string matching with stuck address bits (manuscript)"},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/978-3-540-75520-3_11","volume-title":"Algorithms \u2013 ESA 2007","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., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 99\u2013110. Springer, Heidelberg (2007)"},{"issue":"4","key":"1_CR12","doi-asserted-by":"publisher","first-page":"1444","DOI":"10.1137\/080712969","volume":"39","author":"A. Amir","year":"2009","unstructured":"Amir, A., Hartman, T., Kapah, O., Levy, A., Porat, E.: On the cost of interchange rearrangement in strings. SIAM Journal on Computing\u00a039(4), 1444\u20131461 (2009)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"1_CR13","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/S0020-0190(01)00302-7","volume":"83","author":"A. Amir","year":"2002","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Approximate swapped matching. Information Processing Letters\u00a083(1), 33\u201339 (2002)","journal-title":"Information Processing Letters"},{"key":"1_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1007\/978-3-540-78773-0_5","volume-title":"LATIN 2008: Theoretical Informatics","author":"S. Angelov","year":"2008","unstructured":"Angelov, S., Kunal, K., McGregor, A.: Sorting and selection with random costs. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds.) LATIN 2008. LNCS, vol.\u00a04957, pp. 48\u201359. Springer, Heidelberg (2008)"},{"key":"1_CR15","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V. Bafna","year":"1998","unstructured":"Bafna, V., Pevzner, P.A.: Sorting by transpositions. SIAM Journal on Discrete Mathematics\u00a011, 221\u2013240 (1998)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"1_CR16","unstructured":"Bender, M.A., Ge, D., He, S., Hu, H., Pinter, R.Y., Skiena, S., Swidan, F.: Improved bounds on sorting with length-weighted reversals. In: Proc. 15th SODA, pp. 912\u2013921 (2004)"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","first-page":"32","volume-title":"Combinatorial Pattern Matching","author":"M.A. Bender","year":"2004","unstructured":"Bender, M.A., Ge, D., He, S., Hu, H., Pinter, R.Y., Swidan, F.: Sorting by length-weighted reversals: Dealing with signs and circularity. In: Sahinalp, S.C., Muthukrishnan, S.M., Dogrusoz, U. (eds.) CPM 2004. LNCS, vol.\u00a03109, pp. 32\u201346. Springer, Heidelberg (2004)"},{"key":"1_CR18","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":"1_CR19","first-page":"75","volume-title":"Proc. 1st Annual Intl. Conf. on Research in Computational Biology (RECOMB)","author":"A. Carpara","year":"1997","unstructured":"Carpara, A.: Sorting by reversals is difficult. In: Proc. 1st Annual Intl. Conf. on Research in Computational Biology (RECOMB), pp. 75\u201383. ACM Press, New York (1997)"},{"key":"1_CR20","first-page":"527","volume":"34","author":"A. Cayley","year":"1849","unstructured":"Cayley, A.: Note on the theory of permutations. Philosophical Magazine\u00a0(34), 527\u2013529 (1849)","journal-title":"Philosophical Magazine"},{"key":"1_CR21","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":"1_CR22","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/S0895480197331995","volume":"14","author":"D.A. Christie","year":"2001","unstructured":"Christie, D.A., Irving, R.W.: Sorting strings by reversals and by transpositions. SIAM Journal Discrete Math\u00a014, 193\u2013206 (2001)","journal-title":"SIAM Journal Discrete Math"},{"key":"1_CR23","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":"1_CR24","unstructured":"Fischer, M.J., Paterson, M.S.: String matching and other products. In: Karp, R.M. (ed.) SIAM-AMS Proceedings, Complexity of Computation, vol.\u00a07, pp. 113\u2013125 (1974)"},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A.: Sorting and selection with structured costs. In: Proc. 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 416\u2013425 (2001)","DOI":"10.1109\/SFCS.2001.959916"},{"issue":"1-3","key":"1_CR26","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0166-218X(98)00072-9","volume":"88","author":"L.S. Heath","year":"1998","unstructured":"Heath, L.S., Vergara, J.P.C.: Sorting by bounded block-moves. Discrete Applied Mathematics\u00a088(1-3), 181\u2013206 (1998)","journal-title":"Discrete Applied Mathematics"},{"issue":"5","key":"1_CR27","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1089\/106652703322539097","volume":"10","author":"L.S. Heath","year":"2003","unstructured":"Heath, L.S., Vergara, P.C.: Sorting by short swaps. Journal of Computational Biology\u00a010(5), 775\u2013789 (2003)","journal-title":"Journal of Computational Biology"},{"key":"1_CR28","volume-title":"Computer architecture: A quantitative approach","author":"J.L. Hennessy","year":"2002","unstructured":"Hennessy, J.L., Patterson, D.A.: Computer architecture: A quantitative approach, 3rd edn. Morgan Kauffmann, San Francisco (2002)","edition":"3"},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0304-3975(85)90047-7","volume":"36","author":"M.R. Jerrum","year":"1985","unstructured":"Jerrum, M.R.: The complexity of finding minimum-length generator sequences. Theoretical Computer Science\u00a036, 265\u2013289 (1985)","journal-title":"Theoretical Computer Science"},{"key":"1_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-540-89097-3_22","volume-title":"String Processing and Information Retrieval","author":"O. Kapah","year":"2008","unstructured":"Kapah, O., Landau, G.M., Levy, A., Oz, N.: Interchange rearrangement: The element-cost model. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol.\u00a05280, pp. 224\u2013235. Springer, Heidelberg (2008)"},{"issue":"43","key":"1_CR31","doi-asserted-by":"publisher","first-page":"4315","DOI":"10.1016\/j.tcs.2009.07.013","volume":"410","author":"O. Kapah","year":"2009","unstructured":"Kapah, O., Landau, G.M., Levy, A., Oz, N.: Interchange rearrangement: The element-cost model. Theoretical Computer Science\u00a0410(43), 4315\u20134326 (2009)","journal-title":"Theoretical Computer Science"},{"key":"1_CR32","doi-asserted-by":"crossref","unstructured":"Karp, R., Miller, R., Rosenberg, A.: Rapid identification of repeated patterns in strings, arrays and trees. In: Symposium on the Theory of Computing, vol.\u00a04, pp. 125\u2013136 (1972)","DOI":"10.1145\/800152.804905"},{"key":"1_CR33","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comp.\u00a06, 323\u2013350 (1977)","journal-title":"SIAM J. Comp."},{"key":"1_CR34","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":"1_CR35","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. of the ACM\u00a027, 701\u2013717 (1980)","journal-title":"J. of the ACM"},{"key":"1_CR36","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Some complexity questions related to distributed computing. In: Proc. 11th Annual Symposium on the Theory of Computing (STOC), pp. 209\u2013213 (1979)","DOI":"10.1145\/800135.804414"},{"key":"1_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R. Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, K.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol.\u00a072, pp. 216\u2013226. Springer, Heidelberg (1979)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-12476-1_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:54:25Z","timestamp":1606168465000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-12476-1_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642124754","9783642124761"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-12476-1_1","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-642-12476-1","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}