Compute the edit distance between two words in which substitution is not allowed How do I compute the edit distance between two words in which substitution is not allowed?
The allowed operations include insertion (with cost 1) and deletion (with cost 1), but not substitution.
How is this supposed to be computed without substitution?
You can use the same dynamic programming algorithm as the one for the Levenshtein distance with a bit of modifications.
Let $u=u_1…u_n$ and $v=v_1…v_m$ be two words. We want to build a $(n+1)\times(m+1)$ matrix $M$ such that for $0\leq i\leq n$ and $0\leq j \leq m$, $M[i][j]$ is the edit distance between $u_1…u_i$ (or $\varepsilon$ if $i = 0$) and $v_1…v_j$. The answer is then $M[n][m]$.
Now note that for $0&lt; i\leq n$ and $0&lt; j \leq m$:

if $u_i = v_j$, then $M[i][j] = \min\left\{\begin{array}{rl}M[i-1][j]+1 &amp; (\text{deletion of }u_i)\\M[i][j-1]+1&amp;(\text{insertion of }v_j)\\M[i-1][j-1] &amp; (\text{no modification})\end{array}\right.$
otherwise, $M[i][j] = \min\left\{\begin{array}{rl}M[i-1][j]+1 &amp; (\text{deletion of }u_i)\\M[i][j-1]+1&amp;(\text{insertion of }v_j)\end{array}\right.$