Я пытался вычислить расстояние Левенштейна.Следующий код работает для небольших струн, например, комплект / посадка или сидя / вязание.Но это дало мне ошибку сегментации для строк воскресенье / суббота.После использования GDB (впервые) я понял, что проблема в том, что str2 выходит за пределы выделенного пространства памяти.Но я не смог понять, как.Я потратил много времени на это, сейчас мне кажется, что я смотрю на стену.Может ли кто-нибудь указать на мою ошибку в коде?Спасибо.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// print array of given size
void print_array( char *s_ptr)
{
printf("{");
while(*s_ptr!='\0' && *s_ptr!='\n'){
printf("%c",*s_ptr++);
}
printf("}\n");
}
int min(int a, int b, int c){
int m = a;
//printf("a=%d\tb=%d\tc=%d\n",a,b,c);
if (m > b) m=b;
if (m > c) m=c;
return m;
}
int leven_dist(char str1[], char str2[]){
int len1 = strlen(str1), len2 = strlen(str2);
int dist[len1][len2];
int i,j,ldist;
//int *dist = (int *) malloc(len1*len2*sizeof(int));
for(i=0;i<=len1;i++){
dist[i][0] = i;
printf("dist[%d][0]=%d ",i,dist[i][0]);
}
printf("\tlen1=%d\n",len1);
for(j=0;j<=len2;j++){
dist[0][j] = j;
printf("dist[0][%d]=%d ",j,dist[0][j]);
}
printf("\tlen2=%d\n\n",len2);
for(j=1;j<=len2;j++){
for(i=1;i<=len1;i++){
printf("str1[%d]=%c str2[%d]=%c\n",i-1,str1[i-1],j-1,str2[j-1]);
if(str1[i-1] == str2[j-1]){
dist[i][j] = dist[i-1][j-1];
}
else {
dist[i][j] = min(dist[i-1][j]+1,dist[i][j-1]+1,dist[i-1][j-1]+1);
}
printf("dist[%d][%d]=%d ",i,j,dist[i][j]);
}
printf("\n");
}
for(i=0;i<=len1;i++){
for(j=0;j<=len2;j++){
printf("%d\t",dist[i][j]);
}
printf("\n");
}
ldist= dist[len1][len2];
//free(dist);
return ldist;
}
int main( void )
{
char str1[20]="sunday",str2[20]="saturday";
int ldist=0;
printf("String1:"); print_array(str1);
printf("String2:"); print_array(str2);
//calculate Levenshtein Distance for strings
ldist = leven_dist(str1,str2);
printf("Levenshtein Distance is: %d\n",ldist);
return 0;
}
Вывод
String1:{sunday}
String2:{saturday}
dist[0][0]=0 dist[1][0]=1 dist[2][0]=2 dist[3][0]=3 dist[4][0]=4 dist[5][0]=5 dist[6][0]=6 len1=6
dist[0][0]=0 dist[0][1]=1 dist[0][2]=2 dist[0][3]=3 dist[0][4]=4 dist[0][5]=5 dist[0][6]=6 dist[0][7]=7 dist[0][8]=8 len2=8
str1[0]=s str2[0]=s
dist[1][1]=0 str1[1]=u str2[0]=s
dist[2][1]=1 str1[2]=n str2[0]=s
dist[3][1]=2 str1[3]=d str2[0]=s
dist[4][1]=3 str1[4]=a str2[0]=s
dist[5][1]=4 str1[5]=y str2[0]=s
dist[6][1]=5
str1[0]=s str2[1]=a
dist[1][2]=1 str1[1]=u str2[1]=a
dist[2][2]=1 str1[2]=n str2[1]=a
dist[3][2]=2 str1[3]=d str2[1]=a
dist[4][2]=3 str1[4]=a str2[1]=a
dist[5][2]=3 str1[5]=y str2[1]=a
dist[6][2]=4
str1[0]=s str2[2]=t
dist[1][3]=2 str1[1]=u str2[2]=t
dist[2][3]=2 str1[2]=n str2[2]=t
dist[3][3]=2 str1[3]=d str2[2]=t
dist[4][3]=3 str1[4]=a str2[2]=t
dist[5][3]=4 str1[5]=y str2[2]=t
dist[6][3]=4
str1[0]=s str2[3]=u
dist[1][4]=3 str1[1]=u str2[3]=u
dist[2][4]=2 str1[2]=n str2[3]=u
dist[3][4]=3 str1[3]=d str2[3]=u
dist[4][4]=3 str1[4]=a str2[3]=u
dist[5][4]=4 str1[5]=y str2[3]=u
dist[6][4]=5
Segmentation fault