We are given two strings $x=x_1,x_2,x_3,\ldots,x_m$ and $y=y_1,y_2,y_3,\ldots,y_n$ over some finite alphabet. We consider the problem of converting $x$ to $y$. Using the following operations:
1.Substitution: replace one symbol by another one.
2.Insertion: inserts one symbol
3.Deletion: delete one symbol.
For example, if $x$="logarithm" and $y$="algorithm", we convert $x$ to $y$ in the following way:
start with "logarithm"
inserting "a"at the front gives "alogarithm".
deleting "o"gives "algarithm"
replacing the second "a"by "o"gives "algorithm".
The similarity problem between the string $x$ and $y$ is defined to be the minimum number of operations needed to convert $x$ to $y$.
For example, the similarity between $x$="logarithm" and $y$="algorithm" is 3, because $x$ can be converted to $y$ using three operations. If the string $x$ has length $m$ and the string $y$ is empty, then the similarity between $x$ and $y$ is similar to $m$.
Give a dynamic programming algorithm (in pseudocode) that computes, in $\mathcal o(mn)$ time, the similarity between the string $x$ and $y$.
It is as the edit distance problem but there is the corresponding minimization problem problem where we measure similarity instead of distance .