{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:24:50Z","timestamp":1759638290312,"version":"3.41.0"},"reference-count":12,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2005,10,1]],"date-time":"2005-10-01T00:00:00Z","timestamp":1128124800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2005,10]]},"abstract":"<jats:p>\n            In the Minimum Common String Partition problem (MCSP), we are given two strings on input, and we wish to partition them into the same collection of substrings, minimizing the number of the substrings in the partition. This problem is NP-hard, even for a special case, denoted 2-MCSP, where each letter occurs at most twice in each input string. We study a greedy algorithm for MCSP that at each step extracts a longest common substring from the given strings. We show that the approximation ratio of this algorithm is between \u03a9(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>0.43<\/jats:sup>\n            ) and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>0.69<\/jats:sup>\n            ). In the case of 2-MCSP, we show that the approximation ratio is equal to 3. For 4-MCSP, we give a lower bound of \u03a9(log\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.1145\/1103963.1103971","type":"journal-article","created":{"date-parts":[[2006,2,6]],"date-time":"2006-02-06T15:07:09Z","timestamp":1139238429000},"page":"350-366","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["The greedy algorithm for the minimum common string partition problem"],"prefix":"10.1145","volume":"1","author":[{"given":"Marek","family":"Chrobak","sequence":"first","affiliation":[{"name":"University of California, Riverside, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr","family":"Kolman","sequence":"additional","affiliation":[{"name":"Charles University, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji\u0159\u00ed","family":"Sgall","sequence":"additional","affiliation":[{"name":"Academy of Sciences of the Czech Republic, Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2005.48"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. Lecture Notes in Computer Science","volume":"3122","author":"Chrobak M.","unstructured":"Chrobak , M. , Kolman , P. , and Sgall , J . 2004. The greedy algorithm for the minimum common string partition problem . In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. Lecture Notes in Computer Science , vol. 3122 . Springer, Berlin, Germany, 84--95. Chrobak, M., Kolman, P., and Sgall, J. 2004. The greedy algorithm for the minimum common string partition problem. In Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. Lecture Notes in Computer Science, vol. 3122. Springer, Berlin, Germany, 84--95."},{"volume-title":"Proceedings of the 13th Annual Symposium on Discrete Algorithms. 667--676","author":"Cormode G.","key":"e_1_2_1_3_1","unstructured":"Cormode , G. , and Muthukrishnan , J . 2002. The string edit distance matching with moves . In Proceedings of the 13th Annual Symposium on Discrete Algorithms. 667--676 . Cormode, G., and Muthukrishnan, J. 2002. The string edit distance matching with moves. In Proceedings of the 13th Annual Symposium on Discrete Algorithms. 667--676."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30551-4_43"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.09.012"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11549345_50"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Kruskal J. B. and Sankoff D. 1983. An anthology of algorithms and concepts for sequence comparison. In Time Warps String Edits and Macromolecules: The Theory and Practice of Sequence Comparison D. Sankoff and J. B. Kruskal Eds. Addison-Wesley Reading MA.  Kruskal J. B. and Sankoff D. 1983. An anthology of algorithms and concepts for sequence comparison. In Time Warps String Edits and Macromolecules: The Theory and Practice of Sequence Comparison D. Sankoff and J. B. Kruskal Eds. Addison-Wesley Reading MA.","DOI":"10.1137\/1025045"},{"key":"e_1_2_1_8_1","first-page":"845","article-title":"Binary codes capable of correcting deletions, insertions and reversals","volume":"163","author":"Levenshtein V. I.","year":"1965","unstructured":"Levenshtein , V. I. 1965 . Binary codes capable of correcting deletions, insertions and reversals . Dok. Akad. Nauk SSSR 163 , 4, 845 -- 848 . (in Russian). Levenshtein, V. I. 1965. Binary codes capable of correcting deletions, insertions and reversals. Dok. Akad. Nauk SSSR 163, 4, 845--848. (in Russian).","journal-title":"Dok. Akad. Nauk SSSR"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00268-X"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science","volume":"2373","author":"Shapira D.","unstructured":"Shapira , D. , and Storer , J . 2002. Edit distance with move operations . In Proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science , vol. 2373 . Springer, Berlin, Germany, 85--98. Shapira, D., and Storer, J. 2002. Edit distance with move operations. In Proceedings of the 13th Annual Symposium on Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 2373. Springer, Berlin, Germany, 85--98."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/357401.357404"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(87)90478-5"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1103963.1103971","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1103963.1103971","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:54Z","timestamp":1750286934000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1103963.1103971"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,10]]}},"alternative-id":["10.1145\/1103963.1103971"],"URL":"https:\/\/doi.org\/10.1145\/1103963.1103971","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2005,10]]},"assertion":[{"value":"2005-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}