Skienna's recursive algorithm for edit distance
The two strings s and t are compared starting from the high index,
down to index 1. This is not visible since the initial call to
string_compare is not provided. The i and j arguments for that
initial call are the length of strings s and t.

It should be noted that s and t could be globals, since they are
the same in all calls.

A call to the function string_compare(s,t,i,j) is intended to
compute the minimum edit distance of the prefixes s[1..i] and t[1..j].
It first compares the two strings at indices i and j, and the
recursively at lower indices.

It always tries 3 ways of finding the shortest distance:


by assuming there was a match or a susbstitution edit depending on
whether s[i]==t[j];
by assuming there is an insertion edit of t[j];
by assuming there is an deletion edit of s[i];


Then it computes recursively the sortest distance for the rest of both
strings, and adds 1 to that result, when there is an edit on this call.

When s[i]==t[j] the two strings match on these indices. Hence the
corresponding indices are both decremented, to recursively compute the
shortest distance of the prefixes s[1..i-1] and t[1..j-1]. A
proper match does not increase the distance. Hence
dist(s[1..i],t[1..j])= dist(s[1..i-1], t[1..j-1]).

When s[i]=/=t[j] the two strings do not match, but can be made to
match by a substitution edit. Hence the same recursive call is
possible, but the resulting shortest distance must be incremented by
one for the substitution edit. Hence dist(s[1..i],t[1..j])=
dist(s[1..i-1], t[1..j-1])+1.

That is why the function match returns 0 when there is a match, and
1 when there is none.

Another possibility is not to try for a match, but assume that t[j]
is due to an insertion edit in the case of the smallest distance.
Hence that inserted symbol is ignored by replacing t[1..j] by
t[1..j-1], ie by computing the shortest distance of s[1..i] and
t[1..j-1], which is string_compare(s,t,i,j-1), and then adding 1
for the insertion edit.

The next and last try is the symmetric one, when one assume that the
symbol s[i] was deleted, and thus does not have to appear in t.

The results of the 3 attempts are strored in the array opt, and the
smallest value of the 3 is kept as shortest distance for s[1..i] and
t[1..j].

The decrementations of indices is either because the corresponding
string elements match, or because they have been taken into account by
an edit operation.