{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T16:21:41Z","timestamp":1780330901684,"version":"3.54.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1986,11,1]],"date-time":"1986-11-01T00:00:00Z","timestamp":531187200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1986,11]]},"DOI":"10.1007\/bf01840446","type":"journal-article","created":{"date-parts":[[2005,7,13]],"date-time":"2005-07-13T17:29:13Z","timestamp":1121275753000},"page":"251-266","source":"Crossref","is-referenced-by-count":617,"title":["AnO(ND) difference algorithm and its variations"],"prefix":"10.1007","volume":"1","author":[{"given":"Eugene W.","family":"Myers","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"1","key":"BF01840446_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/321921.321922","volume":"23","author":"A. V. Aho","year":"1976","unstructured":"A. V. Aho, D. S. Hirschberg, and J. D. Ullman. Bounds on the complexity of the longest common subsequence problem.J. ACM,23, 1 (1976), 1\u201312.","journal-title":"J. ACM"},{"key":"BF01840446_CR2","first-page":"203","volume-title":"Data Structures and Algorithms","author":"A. V. Aho","year":"1983","unstructured":"A. V. Aho, J. E. Hopcroft, and J. D. Ullman.Data Structures and Algorithms. Addison-Wesley: Reading, MA, 1983, pp. 203\u2013208."},{"key":"BF01840446_CR3","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra. A note on two problems in connexion with graphs.Numer. Math. 1 (1959), 269\u2013271.","journal-title":"Numer. Math."},{"key":"BF01840446_CR4","doi-asserted-by":"crossref","unstructured":"J. Gosling. A redisplay algorithm.Proceedings ACM SIGPLAN\/SIGOA Symposium on Text Manipulation, 1981, pp.","DOI":"10.1145\/800209.806463"},{"issue":"4","key":"BF01840446_CR5","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1145\/356827.356830","volume":"12","author":"P. A. V. Hall","year":"1980","unstructured":"P. A. V. Hall and G. R. Dowling. Approximate string matching.Comput. Surv. 12, 4 (1980), 381\u2013402.","journal-title":"Comput. Surv."},{"issue":"2","key":"BF01840446_CR6","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"D. Harel and R. E. Tarjan. Fast algorithms for finding nearest common ancestors.SIAM J. Comput.,13, 2 (1984), 338\u2013355.","journal-title":"SIAM J. Comput."},{"issue":"6","key":"BF01840446_CR7","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"D. S. Hirschberg","year":"1975","unstructured":"D. S. Hirschberg. A linear space algorithm for computing maximal common subsequences.Commun. ACM,18, 6 (1975), 341\u2013343.","journal-title":"Commun. ACM"},{"issue":"4","key":"BF01840446_CR8","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"D. S. Hirschberg","year":"1977","unstructured":"D. S. Hirschberg. Algorithms for the longest common subsequence problem.J. ACM 24, 4 (1977), 664\u2013675.","journal-title":"J. ACM"},{"issue":"1","key":"BF01840446_CR9","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/0020-0190(78)90037-6","volume":"7","author":"D. S. Hirschberg","year":"1978","unstructured":"D. S. Hirschberg. An information-theoretic lower bound for the longest common subsequence problem.Inform. Process. Lett. 7, 1 (1978), 40\u201341.","journal-title":"Inform. Process. Lett."},{"key":"BF01840446_CR10","unstructured":"J. W. Hunt and M. D. McIlroy. An algorithm for differential file comparison. Computing Science Technical Report 41, Bell Laboratories (1975)."},{"issue":"5","key":"BF01840446_CR11","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"J. W. Hunt","year":"1977","unstructured":"J. W. Hunt and T. G. Szymanski. A fast algorithm for computing longest common subsequences.Commun. ACM,20, 5 (1977), 350\u2013353.","journal-title":"Commun. ACM"},{"key":"BF01840446_CR12","first-page":"490","volume-title":"The Art of Computer Programming, Vol. 3: Sorting and Searching","author":"D. E. Knuth","year":"1983","unstructured":"D. E. Knuth.The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley: Reading, MA, 1983, pp. 490\u2013493."},{"issue":"1","key":"BF01840446_CR13","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W. J. Masek","year":"1980","unstructured":"W. J. Masek and M. S. Paterson. A faster algorithm for computing string edit distances.J. Comput. System Sci. 20, 1 (1980) 18\u201331.","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"BF01840446_CR14","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E. M. McCreight","year":"1976","unstructured":"E. M. McCreight. A space-economical suffix tree construction algorithm.J. ACM 23, 2 (1976), 262\u2013272.","journal-title":"J. ACM"},{"issue":"11","key":"BF01840446_CR15","doi-asserted-by":"crossref","first-page":"1025","DOI":"10.1002\/spe.4380151102","volume":"15","author":"W. Miller","year":"1985","unstructured":"W. Miller and E. W. Myers. A file comparison program.Software\u2014Practice and Experience,15, 11 (1985), 1025\u20131040.","journal-title":"Software\u2014Practice and Experience"},{"key":"BF01840446_CR16","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF00264437","volume":"18","author":"N. Nakatsu","year":"1982","unstructured":"N. Nakatsu, Y. Kambayashi and S. Yajima. A longest common subsequence algorithm suitable for similar text strings.Acta Inform.,18 (1982), 171\u2013179.","journal-title":"Acta Inform."},{"issue":"4","key":"BF01840446_CR17","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1109\/TSE.1975.6312866","volume":"1","author":"M. J. Rochkind","year":"1975","unstructured":"M. J. Rochkind. The source code control system.IEEE Trans. Software Engrg.,1, 4 (1975), 364\u2013370.","journal-title":"IEEE Trans. Software Engrg."},{"key":"BF01840446_CR18","volume-title":"Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison","author":"D. Sankoff","year":"1983","unstructured":"D. Sankoff and J. B. Kruskal.Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley: Reading, MA, 1983."},{"key":"BF01840446_CR19","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1145\/357401.357404","volume":"2","author":"W. Tichy","year":"1984","unstructured":"W. Tichy. The string-to-string correction problem with block moves.ACM Trans. Comput. Systems,2, (1984), 309\u2013321.","journal-title":"ACM Trans. Comput. Systems"},{"issue":"1","key":"BF01840446_CR20","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. A. Wagner","year":"1974","unstructured":"R. A. Wagner and M. J. Fischer. The string-to-string correction problem.J. ACM 21, 1 (1974), 168\u2013173.","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840446.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01840446\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01840446","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,9]],"date-time":"2019-05-09T15:35:31Z","timestamp":1557416131000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01840446"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,11]]},"references-count":20,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1986,11]]}},"alternative-id":["BF01840446"],"URL":"https:\/\/doi.org\/10.1007\/bf01840446","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,11]]}}}