How can I change this algorithm so the distance only takes into account insertions.
For example: If I have the words CAT and BAT you would need to insert a B in CAT and a C in BAT for the words to be equal so the distance would be 2. The actual algorithm below returns 1 because it allows you to substitute(it also allows for removal). Is there anyway to change the algorithm below to ONLY do insertion? And can anyone provide insight on it?
int LevenshteinDistance(string s, string t)
int len_s = length(s), len_t = length(t)
if(len_s == 0) then return len_t
if(len_t == 0) then return len_s
if(s[len_s-1] == t[len_t-1]) then cost = 0
else cost = 1
return minimum(LevenshteinDistance(s[0..len_s-1], t) + 1,
LevenshteinDistance(s, t[0..len_t-1]) + 1,
LevenshteinDistance(s[0..len_s-1], t[0..len_t-1]) + cost)