String similarity problem
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) &amp;, \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}
    &amp;, \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.