From: Samuel Tardieu <sam@rfc1149.net>
Date: Wed, 19 Nov 2008 08:42:45 GMT
Subject: Re: [PATCH] Fix deletion of last character in levenshtein distance
Message-ID: <2008-11-19-09-42-45+trackit+sam@rfc1149.net>
In-Reply-To: <alpine.DEB.1.00.0811190151000.30769@pacific.mpi-cbg.de>

* 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.