{"id":14722,"date":"2022-05-26T22:08:27","date_gmt":"2022-05-27T02:08:27","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=14722"},"modified":"2026-06-09T11:17:07","modified_gmt":"2026-06-09T15:17:07","slug":"tr-48-constrained-string-editing","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1984\/tr-48-constrained-string-editing\/","title":{"rendered":"TR-48: Constrained String Editing"},"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-48: Constrained String Editing\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n\n\n<p>Carleton University<br><a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1984\/\">Technical Report<\/a>&nbsp;<strong>TR-48<\/strong><br>May 1984<\/p>\n\n\n\n<h2 id=\"constrained-string-editing\" class=\"wp-block-heading\">Constrained String Editing<\/h2>\n\n\n\n<p>J. Oommen<\/p>\n\n\n\n<h3 id=\"abstract\" class=\"wp-block-heading\">Abstract<\/h3>\n\n\n\n<p>Let X and Y be any two strings of finite length. We consider the problem of transforming X to Y using the edit operations of deletion, insertion and substitution. The optimal transformation is the one which has the minimum edit distance associated with it. The problem of computing this distance and the optimal transformation using no edit constraints has been studied in the literature. In this paper we consider the problem of transforming X to Y using any arbitrary edit constraints involving the number and type of edit operations to be performed. An algorithm has been presented to compute the minimum distance associated with editing X to Y subject to the specified constraint. The algorithim requires O(IXI.IYl.min(IXl,IYI)) time and space. The technique to compute the optimal transformation has also been presented.<\/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-48.pdf\">TR-48.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton UniversityTechnical Report&nbsp;TR-48May 1984 Constrained String Editing J. Oommen Abstract Let X and Y be any two strings of finite length. We consider the problem of transforming X to Y using the edit operations of deletion, insertion and substitution. The optimal transformation is the one which has the minimum edit distance associated with it. The [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":11787,"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-14722","page","type-page","status-publish","hentry","cu_page_type-technical-report"],"acf":{"cu_post_thumbnail":""},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14722","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=14722"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14722\/revisions"}],"predecessor-version":[{"id":24558,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/14722\/revisions\/24558"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/11787"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=14722"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=14722"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}