{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T02:44:37Z","timestamp":1725763477504},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642450297"},{"type":"electronic","value":"9783642450303"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-45030-3_6","type":"book-chapter","created":{"date-parts":[[2013,12,12]],"date-time":"2013-12-12T02:32:52Z","timestamp":1386815572000},"page":"55-65","source":"Crossref","is-referenced-by-count":2,"title":["Pattern Matching with Non Overlapping Reversals - Approximation and On-line Algorithms"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benny","family":"Porat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"6_CR1","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/j.jcss.2009.03.001","volume":"75","author":"A. Amir","year":"1995","unstructured":"Amir, A., Aumann, Y., Benson, G., Levy, A., Lipsky, O., Porat, E., Skiena, S., Vishne, U.: Pattern matching with address errors: rearrangement distances. J. Comp. Syst. Sci.\u00a075(6), 359\u2013370 (1995)","journal-title":"J. Comp. Syst. Sci."},{"key":"6_CR2","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1006\/jagm.2000.1120","volume":"37","author":"A. Amir","year":"2000","unstructured":"Amir, A., Aumann, Y., Landau, G., Lewenstein, M., Lewenstein, N.: Pattern matching with swaps. Journal of Algorithms\u00a037, 247\u2013266 (2000) (Preliminary version appeared at FOCS 1997)","journal-title":"Journal of Algorithms"},{"issue":"1","key":"6_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"},{"issue":"3","key":"6_CR4","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0020-0190(98)00151-3","volume":"68","author":"A. Amir","year":"1998","unstructured":"Amir, A., Landau, G.M., Lewenstein, M., Lewenstein, N.: Efficient special cases of pattern matching with swaps. Information Processing Letters\u00a068(3), 125\u2013132 (1998)","journal-title":"Information Processing Letters"},{"key":"6_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-12476-1_1","volume-title":"Algorithms and Applications","author":"A. Amir","year":"2010","unstructured":"Amir, A., Levy, A.: String rearrangement metrics: A survey. In: Elomaa, T., Mannila, H., Orponen, P. (eds.) Ukkonen Festschrift 2010. LNCS, vol.\u00a06060, pp. 1\u201333. Springer, Heidelberg (2010)"},{"key":"6_CR6","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/S089548019528280X","volume":"11","author":"V. Bafna","year":"1998","unstructured":"Bafna, V., Pevzner, P.A.: Sorting by transpositions. SIAM J. on Discrete Mathematics\u00a011, 221\u2013240 (1998)","journal-title":"SIAM J. on Discrete Mathematics"},{"issue":"2","key":"6_CR7","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/S0022-0000(05)80002-9","volume":"48","author":"O. Berkman","year":"1994","unstructured":"Berkman, O., Vishkin, U.: Finding level-ancestors in trees. Journal of Computer and System Sciences\u00a048(2), 214\u2013229 (1994)","journal-title":"Journal of Computer and System Sciences"},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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":"6_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/3-540-45749-6_21","volume-title":"Algorithms - ESA 2002","author":"P. Berman","year":"2002","unstructured":"Berman, P., Hannenhalli, S., Karpinski, M.: 1.375-approximation algorithm for sorting by reversals. In: M\u00f6hring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol.\u00a02461, pp. 200\u2013210. Springer, Heidelberg (2002)"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Carpara, A.: Sorting by reversals is difficult. In: Proc. 1st Annual International Conference on Research in Computational Biology (RECOMB), pp. 75\u201383. ACM Press (1997)","DOI":"10.1145\/267521.267531"},{"key":"6_CR11","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":"6_CR12","unstructured":"Christie, D.A.: A 3\/2-approximation algorithm for sorting by reversals. In: Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 244\u2013252 (1998)"},{"key":"6_CR13","unstructured":"Cole, R., Hariharan, R.: Randomized swap matching in o(m logm log|\u03c3|) time. Technical Report TR1999-789, New York University, Courant Institute (September 1999)"},{"issue":"4","key":"6_CR14","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"},{"issue":"3","key":"6_CR15","doi-asserted-by":"publisher","first-page":"880","DOI":"10.1137\/S0097539798334207","volume":"29","author":"H. Kaplan","year":"1999","unstructured":"Kaplan, H., Shamir, R., Tarjan, R.E.: A faster and simpler algorithm for sorting signed permutations by reversals. SIAM J. Comp.\u00a029(3), 880\u2013892 (1999)","journal-title":"SIAM J. Comp."},{"key":"6_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1007\/3-540-45061-0_73","volume-title":"Automata, Languages and Programming","author":"J. K\u00e4rkk\u00e4inen","year":"2003","unstructured":"K\u00e4rkk\u00e4inen, J., Sanders, P.: Simple linear work suffix array construction. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 943\u2013955. Springer, Heidelberg (2003)"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM Journal of Res. and Dev., 249\u2013260 (1987)","DOI":"10.1147\/rd.312.0249"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-48194-X_17","volume-title":"Combinatorial Pattern Matching","author":"T. Kasai","year":"2001","unstructured":"Kasai, T., Lee, G.H., Arimura, H., Arikawa, S., Park, K.: Linear-time longest-common-prefix computation in suffix arrays and its applications. In: Amir, A., Landau, G.M. (eds.) CPM 2001. LNCS, vol.\u00a02089, pp. 181\u2013192. Springer, Heidelberg (2001)"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching in the presence of errors. In: Proc. 26th IEEE FOCS, pp. 126\u2013126 (1985)","DOI":"10.1109\/SFCS.1985.22"},{"key":"6_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/3-540-60044-2_50","volume-title":"Combinatorial Pattern Matching","author":"S. Muthukrishnan","year":"1995","unstructured":"Muthukrishnan, S.: New results and open problems related to non-standard stringology. In: Galil, Z., Ukkonen, E. (eds.) CPM 1995. LNCS, vol.\u00a0937, pp. 298\u2013317. Springer, Heidelberg (1995)"},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E. Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica\u00a014, 249\u2013260 (1995)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-45030-3_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,4]],"date-time":"2019-08-04T20:27:47Z","timestamp":1564950467000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-45030-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642450297","9783642450303"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-45030-3_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}