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

#define MATCH    +1
#define MISMATCH +0
#define GAP      -2

#define NO_VALUE -10000*GAP

void showUsage() {
  fprintf(stdout, "USAGE: You're doing it wrong !\n");
  exit(1);
}

int max(int v1, int v2) {
  if ( v1 >= v2 )
    return v1;
  else
    return v2;
}

int p(char c1, char c2) {
  if ( c1 == c2 )
    return MATCH;
  else
    return MISMATCH;
}

int *GetLine(char *s, char *t, int line) {
  int *M;
  int i, j;
  int size1, size2;
  int old, temp;

  size1 = strlen(s);
  size2 = strlen(t);

  M = malloc((size2+1) * sizeof(int));

  for ( j = 0; j <= size2; j++ )
    M[j] = j * GAP;

  for ( i = 1; i <= line; i++ )
    {
      old = M[0];
      M[0] = i * GAP;
      
      for ( j = 1; j <= size2; j++ )
	{
	  temp = M[j];
	  
	  M[j] = max(M[j] + GAP, max(old + p(s[i-1], t[j-1]), M[j-1] + GAP));
	  old = temp;
	}
    }
  
  return M;
}

int main(int argc, char **argv) {

  int i, j, k, l;
  
  int *M, old, temp, bValue;
  int size1, size2;

  int *c_line, *u_line;

  char *align_1, *align_2;

  if ( argc != 3 )
    showUsage();

  size1 = strlen(argv[1]); /* Vertical String   */
  size2 = strlen(argv[2]); /* Horizontal String */

  align_1 = malloc((size1 + size2 + 1) * sizeof(char));
  align_2 = malloc((size1 + size2 + 1) * sizeof(char));

  M = malloc((size2+1) * sizeof(int));

  for ( j = 0; j <= size2; j++ )
    M[j] = j * GAP;

  for ( j = 0; j <= size2; j++ )
    fprintf(stdout, "%+03d  ", M[j]);

  fprintf(stdout, "\n");

  for ( i = 1; i <= size1; i++ )
    {
      old = M[0];
      M[0] = i * GAP;

      fprintf(stdout, "%+03d  ", M[0]);
      
      for ( j = 1; j <= size2; j++ )
	{
	  temp = M[j];
	  
	  M[j] = max(M[j] + GAP, max(old + p(argv[1][i-1], argv[2][j-1]), M[j-1] + GAP));
	  old = temp;

	  fprintf(stdout, "%+03d  ", M[j]);
	}

      fprintf(stdout, "\n");
    }

  fprintf(stdout, "\nValue: %d\n", M[size2]);
  bValue = M[size2];

  free(M);
  
  i = size1;
  j = size2;
  k = size1 + size2;
  l = size1 + size2;
  c_line = GetLine(argv[1], argv[2], i);
  u_line = GetLine(argv[1], argv[2], i-1);
  align_1[k--] = '\0';
  align_2[l--] = '\0';

  while ( i != 0 || j != 0 )
    {      
      if ( i == 0 )
	{
	  while ( j > 0 )
	    {
	      align_1[k--] = '-';
	      align_2[l--] = argv[2][j-1];
	      
	      j--;
	    }
	}
      else if ( j == 0 )
	{
	  while ( i > 0 )
	    {
	      align_1[k--] = argv[1][i-1];
	      align_2[l--] = '-';
	      
	      i--;
	    }
	}
      else
	{
	  if ( u_line[j] + GAP == c_line[j] )
	    {
	      align_1[k--] = argv[1][i-1];
	      align_2[l--] = '-';
	    
	      i--;

	      free(c_line);
	      c_line = u_line;
	      u_line = GetLine(argv[1], argv[2], i-1);
	    }
	  else if ( u_line[j-1] + p(argv[1][i-1], argv[2][j-1]) == c_line[j] )
	    {
	      align_1[k--] = argv[1][i-1];
	      align_2[l--] = argv[2][j-1];
	  
	      i--;
	      j--;
	  
	      free(c_line);
	      c_line = u_line;
	      u_line = GetLine(argv[1], argv[2], i-1);
	    }
	  else if ( c_line[j-1] + GAP == c_line[j] )
	    {
	      align_1[k--] = '-';
	      align_2[l--] = argv[2][j-1];

	      j--;
	    }
	  else
	    {
	      fprintf(stdout, "That's funny ...\n");
	      fprintf(stdout, "i=%d j=%d k=%d l=%d\n", i, j, k, l);
	      exit(1);
	    }
	}
    }

  for ( i = k; i >= 0; i-- )
    align_1[i] = ' ';

  for ( i = l; i >= 0; i-- )
    align_2[i] = ' ';

  fprintf(stdout, "s1: %s\n", align_1);
  fprintf(stdout, "s2: %s\n", align_2);

  fprintf(stdout, "\n");

  free(align_1);
  free(align_2);
  free(c_line);
  free(u_line);

  return 0;
}