#include<stdio.h>
#include<string.h>
int cmpADN(char *a,char *b,char *aa,char *bb)
{ int m=strlen(a), n=strlen(b), i, j, F[m+1][n+1];
  for(i=0;i<=m;++i) F[i][0]=i;
  for(j=0;j<=n;++j) F[0][j]=j;
  for(i=0;i<m;++i)
  for(j=0;j<n;++j)
  { int k=(a[i]!=b[j])+F[i][j];
    if(k>F[i+1][j]) k=1+F[i+1][j];
    if(k>F[i][j+1]) k=1+F[i][j+j];
    F[i+1][j+1]=k;
  }
  aa[m]=bb[n]=0;
  for(i=m,j=n;i||j;)
   if(i && F[i][j]>F[i-1][j]) aa[--i]=' '; else
   if(j && F[i][j]>F[i][j-1]) bb[--j]=' '; else
    aa[--i]=b[--j], bb[j]=a[i];
  return F[m][n];
}
int main()
{ char *a="AGGCTAAACGTA", *b="GATTTAGCAGCCGT", aa[1+strlen(a)], bb[1+strlen(b)];
  printf("Il y a %d mutations.\n",cmpADN(a,b,aa,bb));
  printf("%s  %s\n%s  %s\n",a,b,aa,bb);
  return 0;
}