#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>
#include <iostream>
#include <fstream>
#include <math.h>
#define MAX 128
#define SIZE 5
int charGroup[128];
char* letterByGroup;
int** similarity;
char* letters;
int gap;
int insDel;
int gap_limit;
struct Index {
int indexA;
int indexB;
int length;
};
bool Max(std::string a, std::string b){
return a.length() > b.length();
}
int MaxScore(int a, int b, int c){
int max = 0;
if (b >= a){
if(b >= c){
max = b;
} else if(c >= a){
max = c;
} else max = a;
}
if (max < 0)
return 0;
}
void Swap(std::string& a, std::string& b){
std::string buf = a;
a = b;
b = buf;
}
void SpaceErase(std::string &str) {
for(int i = 0; i < str.length(); i++) {
if(str[i] == ' ') {
str.erase(i,1);
i--;
}
}
}
void DefAlphabet(std::istream& in){
std::string buf;
//Считываем штраф за геп, инсерцию-делецию
std::getline(in, buf, ';');
gap = atoi(buf.c_str());
std::getline(in, buf);
std::getline(in, buf, ';');
insDel = atoi(buf.c_str());
std::getline(in, buf); //Проопускаем лишние строки
std::getline(in, buf);
std::getline(in, buf);
//Распределаяем буквы алфавита по "факторгруппам",
//Далее по номеру группы будет происходить обращение к таблице
//для выяснения штрафа
std::string alph;
std::getline(in, alph);
letters = new char[alph.length()/2];
int lettersNumber = 0;
for (int i = 0; i < alph.length(); i++) //
if (alph[i] != ' '){
letters[lettersNumber] = alph[i];
charGroup[alph[i]] = lettersNumber;
lettersNumber++;
}
//Выделяем память для матрицы с очками
// в зависимости от длины алфавита
similarity = new int*[alph.length()];
for (int i = 0; i < alph.length(); i++){
similarity[i] = new int[alph.length()];
}
std::getline(in, buf);
std::getline(in, buf);
//Считываем матрицу
for(int i = 0; i < lettersNumber; i++){
for(int j = 0; j < lettersNumber; j++){
if (j != lettersNumber - 1)
std::getline(in, buf, ' ');
else
std::getline(in, buf);
similarity[i][j] = atoi(buf.c_str());
//std::cout << similarity[i][j] << " ";
}
//std::cout << std::endl;
}
}
void GetLines(std::istream& fs, std::string& a, std::string& b){
std::string seq1 = "", seq2 = "";
std::string name1, name2;
int seq_num = 0;
for (std::string tek_line; std::getline(fs, tek_line); ) {
if (tek_line[0] == '>') {
(seq_num) ? name2 = tek_line : name1 = tek_line;
seq_num++;
continue;
}
SpaceErase(tek_line);
(seq_num > 1) ? seq2 += tek_line : seq1 += tek_line;
}
a = seq1;
b = seq2;
}
int GetScore(std::string a, std::string b){
int result = 0;
for (int i = 0; i < a.length(); i++){
if (a[i] == '-' || b[i] == '-'){
result += gap;
} else {
result += similarity[charGroup[a[i]]][charGroup[b[i]]];
}
}
return result;
}
void FindSubStr(std::string a, std::string b, int i, int j, int** f,
std::string& newA, std::string& newB){
for (int i1 = a.length(); i1 != i; i1--){
newA += '-';
}
for (int j1 = b.length(); j1 != j; j1--){
newB += '-';
}
while (i > 0 && j > 0){
if (f[i][j] == 0)
break;
int scor = f[i][j];
int diag = f[i - 1][j - 1];
int up = f[i][j - 1];
int left = f[i - 1][j];
if (scor == diag + similarity[charGroup[a[i]]][charGroup[b[j]]] ||
gap_limit == 0){
newA = a[i] + newA;
newB = b[j] + newB;
i--;
j--;
} else if(scor == left + gap){
newA = a[i] + newA;
newB = '-' + newB;
i--;
} else if(scor == up + gap){
newA = '-' + newA;
newB = b[j] + newB;
j--;
}
}
while (i > 0){
newA = a[i] + newA;
newB = '-' + newB;
i--;
}
while (j > 0){
newA = '-' + newA;
newB = b[j] + newB;
j--;
}
}
void Align(std::string a, std::string b){
std::cout << a << std::endl;
std::cout << b << std::endl;
int** f = new int*[a.length()];
for (int i = 0; i < a.length(); i++){
f[i] = new int[b.length()];
}
std::cout << "херота" << a << " " << b << std::endl;
std::cout << a << std::endl;
std::cout << b << std::endl;
for (int i = 0; i < a.length(); i++){
f[i][0] = 0;
}
for (int i = 0; i < b.length(); i++){
f[0][i] = 0;
}
int fMax = 0, iMax = 0, jMax = 0;
//заполняем матрицу с путями
for (int i = 1; i < a.length(); i++){
for (int j = 1; j < b.length(); j++){
int match = f[i - 1][j - 1] + similarity[charGroup[a[i]]][charGroup[b[j]]];
int deletion = f[i - 1][j] + gap;
int insertion = f[i][j - 1] + gap;
f[i][j] = MaxScore(match, deletion, insertion);
std::cout << f[i][j] << " ";
if (f[i][j] > fMax){
fMax = f[i][j];
iMax = i;
jMax = j;
}
}
std::cout << std::endl;
}
std::string newA, newB;
int i = a.length() - 1;
int j = b.length() - 1;
std::cout << i<< " "<< iMax << "\n" << j<< " "<< jMax << std::endl;
FindSubStr(a, b, iMax, jMax, f, newA, newB);
std::cout << newA
<< std::endl
<< newB
<< std::endl
<< "New Score "
<< GetScore(newA, newB)
<< std::endl;
}
int main(int argc, char** argv){
if (argc < 3){
std::cout << "type input files" << std::endl;
return 0;
}
//Через аргументы коммандной строки передаются фходные файлы
//Сначала файл с алфавитом, затем файл сo строками
std::ifstream finAlph(argv[1]);
std::ifstream fin(argv[2]);
std::string a, b, buf;
DefAlphabet(finAlph);
//GetLines(fin, a, b);
std::getline(fin, buf);
std::getline(fin, a);
std::getline(fin, buf);
std::getline(fin, buf);
std::getline(fin, b);
std::cout << a << std::endl;
std::cout << b << std::endl;
std::cout << "input gap limit: ";
std::cin >> gap_limit;
Align(a, b);
std::cout << "Old Score " << GetScore(a,b) << std::endl;
return 0;
}