{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T01:25:21Z","timestamp":1791077121264,"version":"4.1.0"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    The problem of comparing two sequences A and B to determine their longest common subsequence (LCS) or the edit distance between them has been much studied. In this paper we consider the following incremental version of these problems: given an appropriate encoding of a comparison between A and B, can one incrementally compute the answer for A and bB, and the answer for A and Bb with equal efficiency, where b is an additional symbol? Our main result is a theorem exposing a surprising relationship between the dynamic programming solutions for two such \"adjacent\" problems. Given a threshold k on the number of differences to be permitted in an alignment, the theorem leads directly to an O(k) algorithm for incrementally computing a new solution from an old one, as contrasts the O(k\n                    <jats:sup>2<\/jats:sup>\n                    ) time required to compute a solution from scratch. We further show, with a series of applications, that this algorithm is indeed more powerful than its nonincremental counterpart. We show this by solving the applications with greater asymptotic efficiency than heretofore possible. For example, we obtain O(nk) algorithms for the longest prefix approximate match problem, the approximate overlap problem, and cyclic string comparison.\n                  <\/jats:p>","DOI":"10.1137\/s0097539794264810","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"557-582","source":"Crossref","is-referenced-by-count":125,"title":["Incremental String Comparison"],"prefix":"10.1137","volume":"27","author":[{"given":"Gad M.","family":"Landau","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eugene W.","family":"Myers","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeanette P.","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/0222017"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0219067"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"J. Gosling,\n                      A Redisplay Algorithm\n                      , Proc. ACM SIGPLAN\/SIGOA Symposium on Text Manipulation, 1991, pp. 123\u2013129.","DOI":"10.1145\/800209.806463"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90176-V"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/356827.356830"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322044"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/359581.359603"},{"key":"R9","unstructured":"J. Kececioglu and E. Myers,\n                      Exact and approximate algorithms for the sequence reconstruction problem\n                      , Algorithmica, 1994, in press."},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Gad Landau, Jeanette Schmidt, An algorithm for approximate tandem repeats, Lecture Notes in Comput. Sci., Vol. 684, Springer, Berlin, 1993, 120\u201313394i:68112","DOI":"10.1007\/BFb0029801"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90045-1"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90010-2"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90109-B"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840446"},{"key":"R16","unstructured":"E. Myers,\n                      Incremental Alignment Algorithms and Their Applications\n                      , Tech. report 86\u201022, Dept. of Computer Science, University of Arizona, Tucson, AZ 85721, 1986."},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/59287.59290"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264437"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0217079"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90016-4"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(81)90087-5"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90023-9"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"P. Weiner,\n                      Linear pattern matching algorithm\n                      , Proc. 14 IEEE Symposium on Switching and Automata Theory, 1973, pp. 1\u201311.","DOI":"10.1109\/SWAT.1973.13"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380150510"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1145\/135239.135244"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539794264810","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:17Z","timestamp":1787335937000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539794264810"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539794264810"],"URL":"https:\/\/doi.org\/10.1137\/s0097539794264810","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}