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:

  1. start with "logarithm"

  2. inserting "a"at the front gives "alogarithm".

  3. deleting "o"gives "algarithm"

  4. 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 .

  • 4
    $\begingroup$ Well, edit distance is equal to the minimal number of operations needed to change one string into another, so that seems to solve your question. $\endgroup$ – Hendrik Jan Dec 2 '12 at 21:11
  • 1
    $\begingroup$ This reads like a homework exercise. What have you tried? $\endgroup$ – Raphael Dec 3 '12 at 11:42

Just like @Hendrik mention all you need to do is calculate Levenshtein distance which does exactly what you need.

Levenshtein distance can be expressed in following formulae $$ \mbox{lev}_{a,b}(i, j) = \begin{cases} \max(i,j) &, \mbox{if } \min(i,j) = 0 \\ \min \begin{cases} \mbox{lev}_{a,b}(i-1,j) +1 \\ \mbox{lev}_{a,b}(i, j-1)+1 \\ \mbox{lev}_{a,b}(i-1,j-1) +[a_i \neq b_i] \end{cases} &, \mbox{else} \end{cases} $$ Where $a, b$ are compared strings, $i, j$ are strings length and $[a_i \neq b_i]$ is $1$ iff $a_i \neq b_i$ and $0$ otherwise.

From this formula it can be easy translated to pseudocode.

Lev(a, b)
  len_a = len(a)
  len_b = len(b)
  cost = 0

  if(a[0] != b[0])
    cost = 1

  if (len_a == 0 or len_b == 0)
    return max(len_a, len_b)
  return min(Lev(a[1..len_a-1], b) + 1,
             Lev(a, b[1..len_b-1]) + 1,
             Lev(a[1..len_a-1], b[1..len_b-1]) + cost)

However there is small problem with this solution, its running time is $\mathcal O(nm)$ and you requested $\mathcal o(nm)$ so I hope you just made a typo.

You can also calculate this distance online using this website.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.