I created an FLL to calculate the Levenshtein distance between two strings. However, when I call it with the strings Kitten and Sitting, the return value isn't always 3. Anybody have any thoughts on what I screwed up?
// // calc_levdist obtained from // http://www.koders.com/c/fid95F7F5D4792831FB74EB61BCD353ECD6DC38A794.aspx, // under GPL /* Copyright (C) 2007 Garrett Fitzgerald This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this software; see the file COPYING. If not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA This software is a derivative work of xphpx Copyright (c) 2001 Free Software Foundation */ // // #include "stdafx.h" #include "pro_ext.h" #ifdef _MANAGED #pragma managed(push, off) #endif int abs (int absVal) { return absVal < 0 ? -1 * absVal : absVal; } static int calc_levdist(const char *s1, const char *s2) /* faster, but obfuscated */ { register char *p1,*p2; register int i,j,n; int l1=0,l2=0; char r[512]; const char *tmp; /* skip equal start sequence, if any */ while(*s1==*s2) { if(!*s1) break; s1++; s2++; } /* if we already used up one string, then the result is the length of the other */ if(*s1=='\0') return strlen(s2); if(*s2=='\0') return strlen(s1); /* length count */ while(*s1++) l1++; while(*s2++) l2++; /* cut of equal tail sequence, if any */ while(*--s1 == *--s2) { l1--; l2--; } /* reset pointers, adjust length */ s1-=l1++; s2-=l2++; /* possible dist to great? */ if(abs(l1-l2)>=255) return -1; /* swap if l2 longer than l1 */ if(l1<l2) { tmp=s1; s1=s2; s2=tmp; l1 ^= l2; l2 ^= l1; l1 ^= l2; } /* fill initial row */ n=(*s1!=*s2); for(i=0,p1=r;i<l1;i++,*p1++=n++,p1++) {/*empty*/} /* calc. rowwise */ for(j=1;j<l2;j++) { /* init pointers and col#0 */ p1 = r + !(j&1); p2 = r + (j&1); n=*p1+1; *p2++=n;p2++; s2++; /* foreach column */ for(i=1;i<l1;i++) { if(*p1<n) n=*p1+(*(s1+i)!=*(s2)); /* replace cheaper than delete? */ p1++; if(*++p1<n) n=*p1+1; /* insert cheaper then insert ? */ *p2++=n++; /* update field and cost for next col's delete */ p2++; } } /* return result */ return n-1; } void EditDist(ParamBlk *parm) { _RetInt(calc_levdist((char *) _HandToPtr(parm->p[0].val.ev_handle), (char *) _HandToPtr(parm->p[1].val.ev_handle)), 4); } FoxInfo myFoxInfo[] = { {"EDITDIST", (FPFI) EditDist, 2, "CC"}, }; extern "C" { FoxTable _FoxTable = { (FoxTable *)0, sizeof(myFoxInfo)/sizeof(FoxInfo), myFoxInfo }; } #ifdef _MANAGED #pragma managed(pop) #endif --- StripMime Report -- processed MIME parts --- multipart/alternative text/plain (text body -- kept) text/html --- _______________________________________________ Post Messages to: [email protected] Subscription Maintenance: http://leafe.com/mailman/listinfo/profox OT-free version of this list: http://leafe.com/mailman/listinfo/profoxtech Searchable Archive: http://leafe.com/archives/search/profox This message: http://leafe.com/archives/byMID/profox/[EMAIL PROTECTED] ** All postings, unless explicitly stated otherwise, are the opinions of the author, and do not constitute legal or medical advice. This statement is added to the messages for those lawyers who are too stupid to see the obvious.
