Given two strings S1 and S2 and three operations (Insert, delete, change) each with different costs, the sequence of operations to convert S1 to S2 is well known as the string editing problem. The minimum cost of transforming S1 to S2 is known as the the 'Edit Distance' between the strings S1 and S2. Computing the edit distance between strings has immense applications, in fact we use edit distance in our day to day life , edit distance is what gets computed when we 'diff' two files. Computing edit script is more general than just computing the edit distance, Hirschberg's algorithm gives a space efficient dynamic programming formulation for computing the edit script, the algorithm is recursive in nature. In this work we implement a non recursive version of the Hirschberg's algorithm. Our context of this problem is to build a highly area efficient VLSI hardware.
Computing the Edit script (minimum cost sequence of INSERT, DELETE and CHANGE) between two strings is a fundamental problem and occurs very frequently. Common UNIX utilities such as 'diff' are based on computing the edit script between tow strings. operations to transform string S1 to S2. I have the following idea to build a nonrecursive version of the Hirschberg's algorithm, since the algorithm is nonrecursive we can build an efficient digital circuit with this idea. We use a simple circular queue and apply DFS (Depth First Search) and we can prove that the capacity of this queue at any stage of the algorithm is θ(log(min(n1,n2)). The proof is simple we choose the geometrically decreasing string which has smaller length from the given strings(
View full history Series and milestones
trunk series is the current focus of development.
All packages Packages in Distributions

libedit source package in Xenial
Version 3.1201503251ubuntu2 uploaded on 20160207 
libedit source package in Trusty
Version 3.1201307122 uploaded on 20130828 
libedit source package in Precise
Version 2.11200806143ubuntu2 uploaded on 20120402 
libedit source package in Disco
Version 3.1201812091 uploaded on 20181212 
libedit source package in Cosmic
Version 3.1201805251 uploaded on 20180530