{"id":14575,"date":"2022-05-09T22:37:45","date_gmt":"2022-05-10T02:37:45","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14575"},"modified":"2026-06-02T14:59:22","modified_gmt":"2026-06-02T18:59:22","slug":"tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982-2\/tr-04-a-practical-longest-common-subsequence-algorithm-for-text-collation\/","title":{"rendered":"TR-04: A Practical Longest Common Subsequence Algorithm for Text Collation"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-04: A Practical Longest Common Subsequence Algorithm for Text Collation\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1982\/\">Technical Report<\/a> <strong>TR-04<\/strong><br>\nJune 1982<\/p>\n\n\n\n<h2 id=\"a-practical-longest-common-subsequence-algorithm-for-text-collation\" class=\"wp-block-heading tr_t1\">A Practical Longest Common Subsequence Algorithm for Text Collation<\/h2>\n\n\n\n<p>Jim des Rivieres<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>Previously published algorithms for finding the longest common subsequence in less than quadratic space are not well suited to the task of finding the differences between long streams of words (text collation). This paper presents a practical incremental algorithm with typical space requirements small enough to allow the handling of large insertions and deletions.<\/p>\n\n\n\n<h3 id=\"download\" class=\"wp-block-heading\">Download<\/h3>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-4.pdf\">TR-04.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-04 June 1982 A Practical Longest Common Subsequence Algorithm for Text Collation Jim des Rivieres Abstract Previously published algorithms for finding the longest common subsequence in less than quadratic space are not well suited to the task of finding the differences between long streams of words (text collation). This paper presents [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11682,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[88],"class_list":["post-14575","page","type-page","status-publish","hentry","cu_page_type-technical-report"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14575","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=14575"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14575\/revisions"}],"predecessor-version":[{"id":14576,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14575\/revisions\/14576"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11682"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=14575"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=14575"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}