{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T23:23:43Z","timestamp":1791069823743,"version":"4.1.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2007,2]]},"abstract":"<jats:p>\n                    The edit distance between two strings\n                    <jats:italic>S<\/jats:italic>\n                    and\n                    <jats:italic>R<\/jats:italic>\n                    is defined to be the minimum number of character inserts, deletes, and changes needed to convert\n                    <jats:italic>R<\/jats:italic>\n                    to\n                    <jats:italic>S<\/jats:italic>\n                    . Given a text string\n                    <jats:italic>t<\/jats:italic>\n                    of length\n                    <jats:italic>n<\/jats:italic>\n                    , and a pattern string\n                    <jats:italic>p<\/jats:italic>\n                    of length\n                    <jats:italic>m<\/jats:italic>\n                    , informally, the string edit distance matching problem is to compute the smallest edit distance between\n                    <jats:italic>p<\/jats:italic>\n                    and substrings of\n                    <jats:italic>t<\/jats:italic>\n                    .\n                  <\/jats:p>\n                  <jats:p>\n                    We relax the problem so that: (a) we allow an additional operation, namely,\n                    <jats:italic>substring moves<\/jats:italic>\n                    ; and (b) we allow approximation of this string edit distance. Our result is a near-linear time deterministic algorithm to produce a factor of\n                    <jats:italic>O<\/jats:italic>\n                    (log\n                    <jats:italic>n<\/jats:italic>\n                    log*\n                    <jats:italic>n<\/jats:italic>\n                    ) approximation to the string edit distance with moves. This is the first known significantly subquadratic algorithm for a string edit distance problem in which the distance involves nontrivial alignments. Our results are obtained by embedding strings into\n                    <jats:italic>L<\/jats:italic>\n                    <jats:sub>1<\/jats:sub>\n                    vector space using a simplified parsing technique, which we call\n                    <jats:italic>edit-sensitive parsing<\/jats:italic>\n                    (ESP).\n                  <\/jats:p>","DOI":"10.1145\/1186810.1186812","type":"journal-article","created":{"date-parts":[[2009,10,13]],"date-time":"2009-10-13T11:10:54Z","timestamp":1255432254000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":102,"title":["The string edit distance matching problem with moves"],"prefix":"10.1145","volume":"3","author":[{"given":"Graham","family":"Cormode","sequence":"first","affiliation":[{"name":"AT&amp;T Labs, Florham Park, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Muthukrishnan","sequence":"additional","affiliation":[{"name":"Rutgers University, Piscataway, NJ"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2007,2,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216067"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 819--828","author":"Alstrup S.","unstructured":"Alstrup , S. , Brodal , G. S. , and Rauhe , T . 2000. Pattern matching in dynamic texts . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 819--828 . Alstrup, S., Brodal, G. S., and Rauhe, T. 2000. Pattern matching in dynamic texts. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 819--828."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 794--803","author":"Amir A.","unstructured":"Amir , A. , Lewenstein , M. , and Porat , E . 2000. Faster algorithms for string matching with k-mismatches . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 794--803 . Amir, A., Lewenstein, M., and Porat, E. 2000. Faster algorithms for string matching with k-mismatches. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 794--803."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/648246.753822"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 463--472","author":"Cole R.","unstructured":"Cole , R. , and Hariharan , R . 1998. Approximate string matching: A simpler, faster algorithm . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 463--472 . Cole, R., and Hariharan, R. 1998. Approximate string matching: A simpler, faster algorithm. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 463--472."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12151"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 197--206","author":"Cormode G.","unstructured":"Cormode , G. , Paterson , M. , Sahinalp , S. C. , and Vishkin , U . 2000. Communication complexity of document exchange . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 197--206 . Cormode, G., Paterson, M., Sahinalp, S. C., and Vishkin, U. 2000. Communication complexity of document exchange. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 197--206."},{"key":"e_1_2_1_8_1","unstructured":"Crochemore M. and Rytter W. 1994. Text Algorithms. Oxford University Press.   Crochemore M. and Rytter W. 1994. Text Algorithms. Oxford University Press."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 769--778","author":"Goel A.","unstructured":"Goel , A. , Indyk , P. , and Varadarajan , K . 2001. Reductions among high dimensional proximity problems . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 769--778 . Goel, A., Indyk, P., and Varadarajan, K. 2001. Reductions among high dimensional proximity problems. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. 769--778."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28429"},{"key":"e_1_2_1_11_1","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"Gusfield D.","unstructured":"Gusfield , D. 1997. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology . Cambridge University Press , New York . Gusfield, D. 1997. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York."},{"key":"e_1_2_1_12_1","volume-title":"Tech. Rep. SRC 1998-011","author":"Henzinger M.","unstructured":"Henzinger , M. , Raghavan , P. , and Rajagopalan , S . 1998. Computing on data streams . Tech. Rep. SRC 1998-011 , DEC Systems Research Centre. Henzinger, M., Raghavan, P., and Rajagopalan, S. 1998. Computing on data streams. Tech. Rep. SRC 1998-011, DEC Systems Research Centre."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796606"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90177-B"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/800152.804905"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90010-2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90178-7"},{"key":"e_1_2_1_20_1","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions and reversals","volume":"10","author":"Levenshtein V. I.","year":"1966","unstructured":"Levenshtein , V. I. 1966 . Binary codes capable of correcting deletions, insertions and reversals . Soviet Physic. Doklady. 10 , 8, 707 -- 710 . Levenshtein, V. I. 1966. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physic. Doklady. 10, 8, 707--710.","journal-title":"Soviet Physic. Doklady."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90002-1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02522825"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335353"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840446"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195164"},{"key":"e_1_2_1_26_1","unstructured":"Sahinalp S. C. and Vishkin U. 1995. Data compression using locally consistent parsing. Tech. Rep. University of Maryland Department of Computer Science.  Sahinalp S. C. and Vishkin U. 1995. Data compression using locally consistent parsing. Tech. Rep. University of Maryland Department of Computer Science."},{"key":"e_1_2_1_27_1","volume-title":"IEEE Conference on the Foundations of Computer Science. 320--328","author":"Sahinalp S. C.","unstructured":"Sahinalp , S. C. , and Vishkin , U . 1996. Efficient approximate and dynamic matching of patterns using a labeling paradigm . In IEEE Conference on the Foundations of Computer Science. 320--328 . Sahinalp, S. C., and Vishkin, U. 1996. Efficient approximate and dynamic matching of patterns using a labeling paradigm. In IEEE Conference on the Foundations of Computer Science. 320--328."},{"key":"e_1_2_1_28_1","unstructured":"Sankoff D. and Kruskal J. B. 1983. Time Warps String Edits and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley.  Sankoff D. and Kruskal J. B. 1983. Time Warps String Edits and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/647821.736368"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1186810.1186812","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T16:33:54Z","timestamp":1672245234000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1186810.1186812"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,2]]},"references-count":29,"aliases":["10.1145\/1219944.1219947","10.1145\/1219944.1219947"],"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,2]]}},"alternative-id":["10.1145\/1186810.1186812"],"URL":"https:\/\/doi.org\/10.1145\/1186810.1186812","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,2]]},"assertion":[{"value":"2007-02-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}