/**************************************************************
 * Algorithmische Bioinformatik - WS 04/05
 *
 * Assignment 2: Compute sub-optimal alignments according to
 *               the Waterman-Eggert algorithm.
 *
 * Sample solution by: Ben Rich (rich@mi.fu-berlin.de)
 *
 * To compile:
 *  > g++ -o watermaneggert watermaneggert.cxx
 *
 * To run:
 *  > ./watermaneggert
 *
 *************************************************************/
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdlib>

using namespace std;


typedef float score_t;

struct EditMatrix
{
	EditMatrix(int rows, int cols) :
		_rows(rows),
		_cols(cols),
		_storage(rows * cols)
	{ }

	score_t& operator() (int i, int j)
	{
		return _storage[(i * _cols)  + j];
	}

private:
	int _rows;
	int _cols;
	vector<score_t> _storage;
};

struct MatrixPos
{
	MatrixPos(int i, int j) :
		row(i), col(j)
	{}

	int row;
	int col;
};

typedef deque<MatrixPos> Path;


inline bool horizontal(Path::iterator it)
{
	return (it->row == (it - 1)->row && it->col == (it - 1)->col + 1);
}

inline bool vertical(Path::iterator it)
{
	return (it->row == (it - 1)->row + 1 && it->col == (it - 1)->col);
}

inline bool diagonal(Path::iterator it)
{
	return (it->row == (it - 1)->row + 1 && it->col == (it - 1)->col + 1);
}

string A, B;
int m, n;
score_t score_match, score_mismatch, gap_penalty;
const char gap_symbol = '-';


void SmithWaterman(EditMatrix& F);
void WatermanEggert(EditMatrix& F, int k);
void correct_path(EditMatrix& F, Path path);
void correct_row_col(EditMatrix& F, int row, int col);
void compute_sw(EditMatrix& F, int i, int j, bool allow_increase=true);
void compute_we(EditMatrix& F, int i, int j);
void get_best(EditMatrix& F, int& best_row, int& best_col);
void traceback(EditMatrix& F, int i, int j, Path& result);
void print_alignment(Path& path);

int main()
{
	int k;

	ifstream input("input.txt");
	if (!input.good())
	{
		cerr << "Hey! Where's the input file?" << endl;
		exit(1);
	}

	input >> A >> B >> score_match >> score_mismatch >> gap_penalty >> k;

	m = A.length();
	n = B.length();

	EditMatrix F(m + 1, n + 1);

	WatermanEggert(F, k);

	return 0;
}

void SmithWaterman(EditMatrix& F)
{
	int i, j;

	for (i=0; i < m + 1; ++i)
	{
		F(i, 0) = 0;
	}
	for (j=0; j < n + 1; ++j)
	{
		F(0, j) = 0;
	}

	for (j=1; j < n + 1; ++j)
	{
		for (i=1; i < m + 1; ++i)
		{
			compute_sw(F, i, j);
		}
	}

}

void WatermanEggert(EditMatrix& F, int k)
{
	int i, j, l;

	SmithWaterman(F);

	Path path;
	get_best(F, i, j);
	traceback(F, i, j, path);
	print_alignment(path);

	for (l=1; l < k; ++l)
	{
		correct_path(F, path);

		path.clear();
		get_best(F, i, j);
		traceback(F, i, j, path);
		print_alignment(path);
	}
}

void correct_path(EditMatrix& F, Path path)
{
	int i, j;
	score_t F_ij;

	Path::iterator it;
	for (it = path.begin(), ++it; it != path.end(); ++it)
	{
		i = it->row;
		j = it->col;
		if (diagonal(it))
		{
			compute_we(F, i, j);
		}
		else
		{
			compute_sw(F, i, j, false);
		}

		correct_row_col(F, i, j);
	}

	if (i < m && j < n )
	{
		do
		{
			++i;
			++j;
			F_ij = F(i, j);
			compute_sw(F, i, j, false);
			correct_row_col(F, i, j);

		} while (F_ij != F(i, j) && i < (m + 1) && j < (n + 1));
	}
}

void correct_row_col(EditMatrix& F, int row, int col)
{
	int i, j;
	score_t F_ij;

	i = row;
	j = col;

	if (j < n)
	{
		do
		{
			++j;
			F_ij = F(i, j);
			compute_sw(F, i, j, false);
		} while (F_ij != F(i, j) && j < (n + 1));
	}

	j = col;

	if (i < m)
	{
		do
		{
			++i;
			F_ij = F(i, j);
			compute_sw(F, i, j, false);
		} while (F_ij != F(i, j) && i < (m + 1));
	}
}


void compute_sw(EditMatrix& F, int i, int j, bool allow_increase=true)
{
	score_t x = 0;
	x = max(x, F(i-1, j) - gap_penalty);
	x = max(x, F(i, j-1) - gap_penalty);
	x = max(x, F(i-1, j-1) + (A[i-1] == B[j-1] ? score_match : score_mismatch));
	if (!allow_increase) x = min(x, F(i, j));
	F(i, j) = x;
}

void compute_we(EditMatrix& F, int i, int j)
{
	score_t x = 0;
	x = max(x, F(i-1, j) - gap_penalty);
	x = max(x, F(i, j-1) - gap_penalty);
	F(i, j) = x;
}

void get_best(EditMatrix& F, int& best_row, int& best_col)
{
	score_t max_value = -1;
	int i, j;
	for (i=0; i < m+1; ++i)
	{
		for (j=0; j < n+1; ++j)
		{
			if (F(i, j) > max_value)
			{
				best_row = i;
				best_col = j;
				max_value = F(i, j);
			}
		}
	}
}

void traceback(EditMatrix& F, int i, int j, Path& result)
{

	while (F(i, j) != 0)
	{
		result.push_front(MatrixPos(i, j));
		if (F(i, j) == F(i - 1, j) - gap_penalty)
		{
			--i;
		}
		else if (F(i, j) == F(i, j - 1) - gap_penalty)
		{
			--j;
		}
		else
		{
			--i;
			--j;
		}
	}
	result.push_front(MatrixPos(i, j));
}

void print_alignment(Path& path)
{
	Path::iterator it;
	for (it = path.begin(), ++it; it != path.end(); ++it)
	{
		if (horizontal(it))
		{
			cout << gap_symbol;
		}
		else
		{
			cout << A[it->row - 1];
		}
	}
	cout << endl;

	for (it = path.begin(), ++it; it != path.end(); ++it)
	{
		if (vertical(it))
		{
			cout << gap_symbol;
		}
		else
		{
			cout << B[it->col - 1];
		}
	}
	cout << endl;
	cout << endl;
}