Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
levenshitein
#include<stdio.h>
#include<string.h>
int min(int a, int b) {
return a<b?a:b;
}
int levenshtein(char *str1,char *str2){
int str1len = strlen(str1);
int str2len = strlen(str2);
char buf1[str1len+1];
char buf2[str2len+1];
char buf3[str1len+1];
char buf4[str2len+1];
strcpy(buf1,str1);
strcpy(buf2,str2);
buf1[str1len-1]='\0';
buf2[str2len-1]='\0';
int i;
for(i=1;i<=str1len;i++){
buf3[i-1]=str1[i];
}
buf3[str1len] = '\0';
for(i=1;i<=str2len;i++){
buf4[i-1]=str2[i];
}
buf4[str2len] = '\0';
if(!strcmp(str1,str2)){
return 0;
}
if(!strcmp(str1,"")){
return str1len;
}
if(!strcmp(str2,"")){
return str2len;
}
printf("%s %s %s %s %s %s\n",str1,str2,buf1,buf2,buf3,buf4);
return min(min(1+levenshtein(buf1,buf2),
min(1+levenshtein(buf1,str2),
1+levenshtein(str1,buf2))),
min(1+levenshtein(buf3,buf4),
min(1+levenshtein(buf3,str2),
1+levenshtein(str1,buf4))));}
int main(void){
char *str1 = "Sunday";
char *str2 = "nday";
int n = levenshtein(str1,str2);
printf("%d\n",n);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment