プログラマ専用SNS ミクプラ

編集距離のプログラムについて、質問です。
editd1の関数については正しく動くのですが、editd2の関数は正しく動きません。
どこが間違っているのかを詳しくお願いしたいです。

コード:

#include <stdio.h>
#define MAX 100

int min(int x[], int n){
  int i;
  int m = x[0];

  for(i=1; i<n; i++){
    if(x[i] < m) m = x[i];
  }
  return m;
}

int dist1[MAX][MAX];

int editd1(char s[],char t[]){
  int m,n,i,j,d[3];

  dist1[0][0] = 0;

  for(m=1; s[m-1] != 0; m++){ 
    dist1[m][0] = m;
  }
  for(n=1; t[n-1] != 0; n++){
    dist1[0][n] = n;
  }

  for(i=1; i<m; i++){
    for(j=1; j<n; j++){
      d[0] = dist1[i-1][j] + 1;
      d[1] = dist1[i][j-1] + 1;
      if(s[i-1] == t[j-1]){
        d[2] = dist1[i-1][j-1];
      }else{
        d[2] = dist1[i-1][j-1] + 1;
      }
      dist1[i][j] = min(d,3);
    }
  }
  return dist1[m-1][n-1];
}

int dist2[2][MAX];

int editd2(char s[],char t[]){
  int n,i,j,d[3];

  dist2[0][0] = 0;
  for(n=1; t[n-1] != 0; n++) dist2[0][n] = n;
  for(i=1; s[i-1] != 0; i++){
    dist2[i % 2][0] = i; //0,1,0,1...
    for(j=1; j<n; j++) {
      d[0] = dist2[(i-1) % 2][j] + 1;
      d[1] = dist2[i % 2][j-1] + 1;
      d[2] = dist2[(i-1) % 2][j-1] + (s[i-1] == t[j-1] ? 1:0);
      dist2[i % 2][j] = min(d,3);
    }
  }
  return dist2[i % 2][n-1];
}

int main(void){
  char s[] = "abcd";
  char t[] = "player";
  int d,d2;

  d = editd1(s,t); 
  d2 = editd2(s,t); 

  printf("d = %d\n",d);
  printf("d2 = %d\n",d2);

  return 0;
}

プラプラさんが書きました:editd1の関数については正しく動くのですが、editd2の関数は正しく動きません。
どこが間違っているのかを詳しくお願いしたいです。

d[2] を求めるとき、
edit1 では、s[i-1] == t[j-1] でないときに +1 しているのに、
edit2 では、s[i-1] == t[j-1] であるときに +1 しているからでは？

回答ありがとうございます。
修正したら、きちんと動きました。

プログラマ専用SNS ミクプラ

編集距離について

編集距離について

Re: 編集距離について

Re: 編集距離について