fork download 
  1. #include <stdio.h>
  2.  
  3. #define d(i,j) dd[(i) * (m+2) + (j) ]
  4. #define min(x,y) ((x) < (y) ? (x) : (y))
  5. #define min3(a,b,c) ((a)< (b) ? min((a),(c)) : min((b),(c)))
  6. #define min4(a,b,c,d) ((a)< (b) ? min3((a),(c),(d)) : min3((b),(c),(d)))
  7.  
  8. int dprint(int* dd, int n,int m){
  9.  int i,j;
  10.  for (i=0; i < n+2;i++){
  11.     for (j=0;j < m+2; j++){
  12.         printf("%02d ",d(i,j));
  13.     }
  14.     printf("\n");
  15.  }
  16.  printf("\n");
  17.  return 0;
  18. }
  19.  
  20. int dldist2(char *s, char* t, int n, int m) {
  21.     int *dd;
  22.     int i, j, cost, i1,j1,DB;
  23.     int INFINITY = n + m;
  24.     static int DA[256 * sizeof(int)];
  25.  
  26.     memset(DA, 0, sizeof(DA));
  27.  
  28.     if (!(dd = (int*) malloc((n+2)*(m+2)*sizeof(int)))) {
  29.       printf("malloc error\n");
  30.       return -1;
  31.     }
  32.  
  33.     d(0,0) = INFINITY;
  34.     for(i = 0; i < n+1; i++) {
  35.       d(i+1,1) = i ;
  36.       d(i+1,0) = INFINITY;
  37.     }
  38.     for(j = 0; j<m+1; j++) {
  39.       d(1,j+1) = j ;
  40.       d(0,j+1) = INFINITY;
  41.     }      
  42. //    dprint(dd,n,m);
  43.  
  44.     for(i = 1; i< n+1; i++) {
  45.       DB = 0;
  46.       for(j = 1; j< m+1; j++) {
  47.         i1 = DA[t[j-1]];
  48.         j1 = DB;
  49.         cost = ((s[i-1]==t[j-1])?0:1);
  50.         if(cost==0) DB = j;
  51.         d(i+1,j+1) =
  52.           min4(d(i,j)+cost,
  53.               d(i+1,j) + 1,
  54.               d(i,j+1)+1, 
  55.               d(i1,j1) + (i-i1-1) + 1 + (j-j1-1));
  56.       }
  57.       DA[s[i-1]] = i;
  58. //      dprint(dd,n,m);
  59.     }
  60.     cost = d(n+1,m+1);
  61.     free(dd);
  62.     return cost;
  63. }
  64.  
  65. int main(void) {
  66. 	int cost;
  67. 	int msize;
  68. 	int nsize;
  69.  
  70. 	msize = 8;
  71. 	nsize = 8;
  72. 	cost = dldist2("ABNANA", "BANANA", nsize, msize);
  73. 	printf("%.3f\n", cost / (float)(nsize * msize));
  74. 	msize = 16;
  75. 	nsize = 16;
  76. 	cost = dldist2("ABNANA", "BANANA", nsize, msize);
  77. 	printf("%.3f\n", cost / (float)(nsize * msize));
  78.  
  79. 	return 0;
  80. }
  81.  
Success #stdin #stdout 0s 2304KB
comments (?)
stdin 
Standard input is empty
stdout 
0.031
0.035
https://ideone.com/HFEmDT
C
language:
C (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!