11065: 【原1065】小M的生物实验1

题目描述

author: wcy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1065

Description

DNA分子是由4种碱基A、T、C、G按照一定次序排列成的。小M现在的任务是要将提取出的某两种生物体的DNA片段进行对比，求出其相似程度。

Sample Input1

CTT
CAT


Sample Output1

2


Sample Input2

TATGCAATAATAATTTTGCTTAGTCCTGGTGCGCGCTGGCGTTATAG
CACCCCGAATATGCGGCACTCCGCTGATAATGGCAAACACAGCGCGCAATG


Sample Output2

27


FineArtz's solution

/* 小M的生物实验 */
#include <iostream>
#include <cstring>
using namespace std;

int f[1005][1005] = {0};
char s1[1005], s2[1005];

int main(){
cin >> s1 >> s2;
int l1 = strlen(s1), l2 = strlen(s2);
for (int i = 0; i <= l1; ++i){
for (int j = 0; j <= l2; ++j){
if (i == 0 || j == 0)
f[i][j] = 0;
else if (s1[i - 1] == s2[j - 1])
f[i][j] = f[i - 1][j - 1] + 1;
else
f[i][j] = max(f[i][j - 1], f[i - 1][j]);
}
}
cout << f[l1][l2] << endl;
return 0;
}


yyong119's solution

#include <iostream>
#include <cstring>
using namespace std;
char p[1001], q[1001];
int i, j, lp, lq, maxlen;
int f[1001][1001];
int main() {
cin>>p>>q;
lp = strlen(p); lq = strlen(q);
for (i = 1; i <= lp; i++)
for (j = 1; j <= lq; j++){
if (p[i - 1] != q[j - 1]){
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
} else {
f[i][j] = f[i - 1][j - 1] +1;
}
}
for (i = 0; i <= lp; i++)
for (j = 0; j <= lq; j++)
maxlen  = max(maxlen, f[i][j]);
cout<<maxlen;
}