//03-170609
//?????¶????´?
//kawashima-tomoki003@g.ecc.u-tokyo.ac.jp

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

int read_file(char *fname,char **buf)
{
  int n;
  char *p;
  FILE *fin;
  fin=fopen(fname,"r");
  if(fin==NULL){
    printf("cannot open %s\n",fname);
    exit(1);
  }
  fseek(fin,0,SEEK_END);
  n=ftell(fin)-1;
  fseek(fin,0,SEEK_SET);
  p=malloc(n*sizeof(char));
  if(p==NULL){
    printf("not enough memory\n");
    exit(1);
  }
  fread(p,sizeof(char),n,fin);
  fclose(fin);
  *buf=p;
  return n;
}

void print(int **A,int n,int m)
{
  int i;
  int j;
  for(i=0;i<=n;i++){
    for(j=0;j<=m;j++){
      printf("%d",A[i][j]);
        if(j<m){
          printf(" ");
        }
    }
    printf("\n");
  }
}

int min(int x,int y,int z)
{
  int n;
  if(x<y){
    n=x;
  }else{
    n=y;
  }
  if(z<n) n=z;
  return n;
}

int sm(int n,int m,char *X,char *Y)
{
  int **A;
  int i,j;
  int c1,c2,c3;
  A=malloc((n+1)*sizeof(int*));
  for(i=0;i<=n;i++){
    A[i]=malloc((m+1)*sizeof(int));
  }

  //0??????0???????????????./
  for(i=0;i<=n;i++){
    A[i][0]=2*i;
    A[0][i]=2*i;
  }

  for(i=1;i<=n;i++){
    for(j=1;j<=m;j++){
      if(X[i-1]==Y[j-1]) c1=A[i-1][j-1];
      if(X[i-1]!=Y[j-1]) c1=A[i-1][j-1]+1;
      c2=A[i][j-1]+2;
      c3=A[i-1][j]+2;
      A[i][j]=min(c1,c2,c3);
    }
  }
  return A[n][m];
}


int main(int argc,char *argv[])
{
  int n,m;
  int i,c;
  FILE *fin;
  char *X,*Y;

  if(argc<3){
    printf("%s file1 file2\n",argv[0]);
    return 1;
  }
  n=read_file(argv[1],&X);
  m=read_file(argv[2],&Y);
  printf("n=%d,m=%d\n",n,m);
  c=sm(n,m,X,Y);
  printf("%d\n",c);
  return 0;
}