diff options
| -rw-r--r-- | ext/standard/levenshtein.c | 26 | ||||
| -rw-r--r-- | ext/standard/tests/general_functions/003.phpt | 6 |
2 files changed, 18 insertions, 14 deletions
diff --git a/ext/standard/levenshtein.c b/ext/standard/levenshtein.c index 47a8de7540..f5c23687cf 100644 --- a/ext/standard/levenshtein.c +++ b/ext/standard/levenshtein.c @@ -40,33 +40,31 @@ static int reference_levdist(const char *s1, int l1, if((l1>LEVENSHTEIN_MAX_LENTH)||(l2>LEVENSHTEIN_MAX_LENTH)) return -1; - if(!(p1=emalloc(l2*sizeof(int)))) { + if(!(p1=emalloc((l2+1)*sizeof(int)))) { return -2; } - if(!(p2=emalloc(l2*sizeof(int)))) { + if(!(p2=emalloc((l2+1)*sizeof(int)))) { free(p1); return -2; } - p1[0]=(s1[0]==s2[0])?0:cost_rep; + for(i2=0;i2<=l2;i2++) + p1[i2] = i2*cost_ins; - for(i2=1;i2<l2;i2++) - p1[i2]=i2*cost_ins; - - for(i1=1;i1<l1;i1++) + for(i1=0;i1<l1;i1++) { - p2[0]=i1*cost_del; - for(i2=1;i2<l2;i2++) + p2[0]=p1[0]+cost_del; + for(i2=0;i2<l2;i2++) { - c0=p1[i2-1]+((s1[i1]==s2[i2])?0:cost_rep); - c1=p1[i2]+cost_del; if(c1<c0) c0=c1; - c2=p2[i2-1]+cost_ins; if(c2<c0) c0=c2; - p2[i2]=c0; + c0=p1[i2]+((s1[i1]==s2[i2])?0:cost_rep); + c1=p1[i2+1]+cost_del; if(c1<c0) c0=c1; + c2=p2[i2]+cost_ins; if(c2<c0) c0=c2; + p2[i2+1]=c0; } tmp=p1; p1=p2; p2=tmp; } - c0=p1[l2-1]; + c0=p1[l2]; efree(p1); efree(p2); diff --git a/ext/standard/tests/general_functions/003.phpt b/ext/standard/tests/general_functions/003.phpt index 22cbd4eb4e..141b4d7052 100644 --- a/ext/standard/tests/general_functions/003.phpt +++ b/ext/standard/tests/general_functions/003.phpt @@ -47,6 +47,12 @@ $n += test_me("bug #6562", 1, "ddebug", "debug"); $n += test_me("bug #6562", 2, "debbbug", "debug"); $n += test_me("bug #6562", 1, "debugging", "debuging"); +$n += test_me("bug #16473", 2, "a", "bc"); +$n += test_me("bug #16473", 2, "xa", "xbc"); +$n += test_me("bug #16473", 2, "xax", "xbcx"); +$n += test_me("bug #16473", 2, "ax", "bcx"); + + echo ($n==0)?"all passed\n":"$n failed\n"; ?> |