табуляция = 2 пробела

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include "DataReader.h"
#define DEBUG
void PrintWay(int** way, int i, int j, std::string &seq1, std::string &seq2,
std::string &result1, std::string &result2
) {
if (i < 1 || j < 1) {
while (i) {
i--;
result2.insert(0, 1, seq2[i]);
result1.insert(0, 1, ' ');
}
while (j) {
j--;
result2.insert(0, 1, ' ');
result1.insert(0, 1, seq1[j]);
}
return;
}
//std::cout << i << ' ' << j << std::endl;
if (way[i][j] == 1) { i--; j--; result1.insert(0, 1, seq1[j]); result2.insert(0, 1, seq2[i]); }
else if (way[i][j] == 2) { i--; result1.insert(0, 1, '-'); result2.insert(0, 1, seq2[i]); }
else { j--; result1.insert(0, 1, seq1[j]); result2.insert(0, 1, '-'); }
PrintWay(way, i, j, seq1, seq2, result1, result2);
}
int main(int argc, char** argv) {
if (argc < 4) {
std::cout << "Need more arguments!" << std::endl;
return 0;
}
//Входные данные
std::string name1, name2, seq1, seq2, alphabet;
int index_array[128];
int** score_matrix = ReadData(name1, seq1, name2, seq2, alphabet, index_array,
argv[1], argv[2]);
//Последний аргумент - штраф за вставку/удаление------------------------------
int penalty = atoi(argv[3]);
#ifdef DEBUG
std::cout << name1 << std::endl << seq1 << std::endl;
std::cout << name2 << std::endl << seq2 << std::endl;
std::cout << ">alphabet" << std::endl << alphabet << std::endl;
std::cout << ">score matrix" << std::endl;
for (int i = 0; i < alphabet.length(); i++) {
for (int j = 0; j < alphabet.length(); j++) {
std::cout << score_matrix[i][j] << " ";
}
std::cout << std::endl;
}
std::cout << ">penalty" << std::endl << penalty << std::endl << std::endl;
#endif
//Алгоритм====================================================================
int** score = new int* [seq2.length() + 1];
int** way = new int* [seq2.length() + 1];
for (int i = 0; i < seq2.length() + 1; i++) {
score[i] = new int [seq1.length() + 1];
way[i] = new int [seq1.length() + 1];
memset(score[i], 0, sizeof(int)*(seq1.length() + 1));
memset(way[i], 0, sizeof(int)*(seq1.length() + 1));
}
for (int i = 1; i < seq2.length() + 1; i++) {
for (int j = 1; j < seq1.length() + 1; j++) {
//оставить все как есть
int way1 = score[i-1][j-1] +
score_matrix[ index_array[seq2[i-1]] ][ index_array[seq1[j-1]] ];
//порвать seq1
int way2 = score[i-1][j] + penalty;
//порвать seq2
int way3 = score[i][j-1] + penalty;
//выбираем максимум
if (way1 >= way2 && way1 >= way3) {
score[i][j] = way1;
way[i][j] = 1;
} else if (way2 >= way1 && way2 >= way3) {
score[i][j] = way2;
way[i][j] = 2;
} else {
score[i][j] = way3;
way[i][j] = 3;
}
}
}
#ifdef DEBUG
for (int i = 0; i < seq2.length() + 1; i++) {
for (int j = 0; j < seq1.length() + 1; j++) {
std::cout.width(4);
std::cout << score[i][j] << ' ';
}
std::cout << std::endl;
}
std::cout << std::endl;
for (int i = 0; i < seq2.length() + 1; i++) {
for (int j = 0; j < seq1.length() + 1; j++) {
std::cout << way[i][j] << ' ';
}
std::cout << std::endl;
}
std::cout << std::endl;
#endif
std::string result1, result2;
int max_score = score[seq2.length()][0], finish = 0;
for (int j = 1; j <= seq1.length(); j++) {
if (score[seq2.length()][j] > max_score) {
max_score = score[seq2.length()][j];
finish = j;
}
}
PrintWay(way, seq2.length(), finish, seq1, seq2, result1, result2);
result1.insert(result1.length(), seq1, finish, seq1.length());
std::cout << result1 << std::endl;
std::cout << result2 << std::endl;
std::cout << std::endl << ">score" << std::endl;
std::cout << max_score << std::endl;
//Конец=======================================================================
for (int i = 0; i < alphabet.length(); i++) {
delete[] score_matrix[i];
}
for (int i = 0; i < seq2.length() + 1; i++) {
delete[] score[i];
delete[] way[i];
}
delete[] score_matrix;
delete[] score;
delete[] way;
return 0;
}