Levenshtein distance with non uniform cost for insertions and substitutions:
<p>I have been trying to implement a levenshtein distance function in C++ that gives different weights to substitutions and insertions based on which characters are being replaced or inserted. </p>

<p>The cost is calculated based on the distance of the keys on an qwerty keyboard. For example, in the standard edit distance algorithm, the distance between google, hoogle, and zoogle is the same; 1. What I want is different distances for these. Something like google -> hoogle = 1, google -> zoogle = 4, hoogle -> zoogle = 5. </p>

<p>I followed the <a href="https://en.wikipedia.org/wiki/Levenshtein_distance#Iterative_with_full_matrix" rel="nofollow">Wikipedia algorithm</a> using the matrix for memoization and implemented it in c++. Here is my function.</p>

<pre><code>int levDist(string s, string t) {

    int i,j,m,n,temp,subsitutionCost, deletionCost, insertionCost, keyDist;
    deletionCost = 1;

    m = s.length();
    n = t.length();
    int d[m+1][n+1];

    for(i=0;i&lt;=m;i++)
        d[i][0] = i;
    for(j=0;j&lt;=n;j++)
        d[0][j] = j;

    for (j=1;j&lt;=n;j++)
    {
        for(i=1;i&lt;=m;i++)
        {
            // getKeyboardDist(char a, char b) gives distance b/w the two keys
            keyDist = getKeyboardDist(s[i-1],t[j-1]); 

            subsitutionCost = (s[i-1] == t[j-1]) ? 0 : keyDist;

            // this line is the one i think the problem lies in
            insertionCost = (i &gt; j) ? getKeyboardDist(s[i-1],t[j-2]) : getKeyboardDist(s[i-2],t[j-1]);


            insertionCost = insertionCost ? insertionCost : 1;

            d[i][j] = min((d[i-1][j]   + deletionCost),
                      min((d[i][j-1]   + insertionCost),
                          (d[i-1][j-1] + subsitutionCost)));`
        }
    }
    return d[m][n];
}
</code></pre>

<p>Now the subsitutions work properly I beleive, but the problem is the insertions. I dont know how to find which characters to get the distance between for insertions. Especially the cases when the insertion is in the beginning or end of the string.</p>

<p>I would appreciate any help in this, let me know if there is any other information needed.</p>

<p>Thanks in advance.</p>