アラインメントのプログラム。
トレースバックはなし。
入力形式は
match時の得点 unmatch時の得点 gapの得点
比較するもとの文字列
比較対象の文字列
とする。例えば
2 -1 -2
aaa
aabba
#include <string>
#include <iostream>
#define VALUE int
using namespace std;
VALUE max(VALUE, VALUE);
VALUE matching(char, char);
static VALUE match, unmatch, gap;
int main(){
string str1, str2; // 比較元の文字列と比較対象の文字列
cin >> match >> unmatch >> gap >> str1 >> str2;
VALUE matrix[str1.size()+1][str2.size()+1];
for(int i=0; i<str1.size(); i++){ // 0列目の初期化
matrix[i][0] = i*gap;
}
for(int i=0; i<str2.size()+1; i++){ // 0行目の初期化
matrix[0][i] = i*gap;
}
for(int j=1; j<str1.size()+1; j++){
for(int i=1; i<str2.size()+1; i++){
matrix[j][i] = max(matrix[j-1][i-1]+matching(str1[j-1],str2[i-1]), max(matrix[j-1][i]+gap, matrix[j][i-1]+gap));
}
}
cout << "result = " << matrix[str1.size()][str2.size()] << endl;
}
VALUE max(VALUE a, VALUE b){
if(a>=b){
return a;
}else{
return b;
}
}
VALUE matching(char a, char b){
if(a==b){
return match;
}else{
return unmatch;
}
}
最終更新:2009年12月22日 15:34