#include <iostream>
#include <string>
#include <fstream>

using namespace std;

struct cell{
  int score;
  int up;
  int left;
  int diagonal;
};

int scoring(char a, char b){
  
  int score;
  if (a == b && a != '-')
    score=2;
  if (a == b && a == '_')
	score=0;
  if (a != b)
	score=-1;
  
  return score;
}

cell** table(string a, string b){

  int rows = a.length();
  int columns = b.length();
  int i=0;
  int j=0;								
  int score1=0; 
  int score2=0;
  int score3=0;			
  
  cell **V;			
  V = new cell*[rows+1]; 
	
  if (V == NULL){
    cerr << "out of memory\n"; 
	exit (1); 
  }

  for (i = 0; i <= rows; i++) { 
    V[i] = new cell[columns+1];
    if (V[i] == NULL){
	cerr << "out of memory\n";
	exit (1);
    }    
  }

  for (j=1; j<=columns; j++){
    V[0][j].score = V[0][j-1].score + scoring(b[j-1],'-');
	V[0][j].left=1;
	V[0][j].diagonal=0;
	V[0][j].up=0;
	}

  for (i=1; i<=rows; i++){
    V[i][0].score = V[i-1][0].score + scoring(a[i-1],'-');
	V[i][0].left=0;
	V[i][0].diagonal=0;
	V[i][0].up=1;
	}

  for(i=1; i<=rows; i++){
    for (j=1; j<=columns; j++){
	  score1 = scoring(a[i-1], b[j-1]) + V[i-1][j-1].score;
	  score2 = scoring(a[i-1], '-') + V[i][j-1].score;
	  score3 = scoring(b[j-1], '-') + V[i-1][j].score;
      
      V[i][j].score = score1;
	  V[i][j].diagonal=0;
	  V[i][j].left=0;
	  V[i][j].up=0;

	  if (score2 > V[i][j].score)
        V[i][j].score = score2;
      if (score3 > V[i][j].score)
        V[i][j].score = score3;
      if (score1 == V[i][j].score)
        V[i][j].diagonal=1;
      if (score2 == V[i][j].score)
		V[i][j].left=1;
      if (score3 == V[i][j].score)
		V[i][j].up=1;
      }
	}
	return V;
}

void trace(cell **V, string a, string b, string &aoptimal, string &boptimal, int row, int column){

  if (V[row][column].diagonal == 1){
	row--;
	column--;
	trace(V,a,b,aoptimal,boptimal,row,column);
	boptimal+=b[column];
	aoptimal+=a[row];
	}
    else if (V[row][column].up == 1){
	  row--;
	  trace(V,a,b,aoptimal,boptimal,row,column);
	  boptimal+="-";
	  aoptimal+=a[row];
	}
	else if (V[row][column].left == 1){
	  column--;
	  trace(V,a,b,aoptimal,boptimal,row,column);
	  boptimal+=b[column];
	  aoptimal+="-";
 	}


}   

int main () {
	
  string sequence1;
  string sequence2;
  string aoptimal;
  string boptimal;
  cell** V;

  ifstream inStr("test.txt");
    if (!inStr) {
      cerr << "file not found" << endl;
	  exit(1);
	}

  getline(inStr, sequence1);
  getline(inStr, sequence2);

  int    row = sequence1.length();
  int column = sequence2.length();
  
  // I know for sure that the code for this is correct and it should print the value for the 
  // value of the last cell.  When I compile it in Devc++ a strange number appears
  // which I didn't know if it was the compiler used or if I didn't intialize it to 
  // or something.
  
  V = table(sequence1, sequence2);
  cout << "The optimal alignment score for " << sequence1 << " and " << sequence2
  << " is " << V[sequence1.length()][sequence2.length()].score << endl << endl;
  
  // could only get one trace to work
  trace(table(sequence1, sequence2),sequence1,sequence2,aoptimal,boptimal,row,column);
  cout<< "Optimal alignment(s) for the sequences " << sequence1 << " and " << sequence2
  << " is/are\n\n" << aoptimal <<endl << boptimal <<endl<<endl;

  system ("PAUSE");
  return 0;
	
}