Re: [PATCH] Fix deletion of last character in levenshtein distance

* Johannes Schindelin <Johannes.Schindelin@gmx.de> [2008-11-19 01:53:45 +0100]

| Hi,
| 
| On Tue, 18 Nov 2008, Samuel Tardieu wrote:
| 
| > diff --git a/levenshtein.c b/levenshtein.c
| > index db52f2c..98fea72 100644
| > --- a/levenshtein.c
| > +++ b/levenshtein.c
| > @@ -25,7 +25,7 @@ int levenshtein(const char *string1, const char *string2,
| >  					row2[j + 1] > row0[j - 1] + w)
| >  				row2[j + 1] = row0[j - 1] + w;
| >  			/* deletion */
| > -			if (j + 1 < len2 && row2[j + 1] > row1[j + 1] + d)
| > +			if (row2[j + 1] > row1[j + 1] + d)
| 
| I do not understand: does row2 have more entries than len2?

Yes it does: int *row2 = xmalloc(sizeof(int) * (len2 + 1));

| In any case, you will _have_ to guard against accessing elements
| outside the reserved memory.

Why would that be needed? j belongs to [0, len2[, so j+1 is always in [0, len2+1[ which is ok for both row2 and row1.