#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int ADN(char *a, char *b, char *ta, char *tb)
{ const int N=strlen(a), M=strlen(b);
  int F[N+1][M+1], min, i, j;

  for(i=0;i<=N;i++) F[i][0]=i;

  for(j=0;j<=M;j++) F[0][j]=j;

  for(i=1;i<=N;i++)
  for(j=1;j<=M;j++)
  if (a[i-1]==b[j-1]) F[i][j]=F[i-1][j-1];
  else
              {
                  min=F[i-1][j-1];
                  if(min>F[i-1][j]) min=F[i-1][j];
                  if(min>F[i][j-1]) min=F[i][j-1];
                  F[i][j]=min+1;
              }

  for(ta[i=N]=tb[j=M]=0;i || j;)
  if(i && F[i][j]>F[i-1][j]) ta[--i]=' '; else
  if(j && F[i][j]>F[i][j-1]) tb[--j]=' '; else
  i--, j--,  ta[i]=tb[j]= a[i]==b[j] ? a[i] : '*';

  return F[N][M];
}

int main()
{ char A[]="ACCTGACA", B[]="CACGACTA", TA[strlen(A)+1], TB[strlen(B)+1];
  int d=ADN(A,B,TA,TB);
  printf("%s %s\n%s %s\n%d\n",A,B,TA,TB,d);
  system("pause");
  return 0;
}