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

题目

题目描述

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

Description

小M最近在做和遗传生物学有关的实验。具体过程是这样的，小M从若干种生物体内提取DNA片段，并对其进行测序。

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

相似程度是用两个碱基序列的最大公共子序列的长度表述的。

Input Format

输入共两行，分别是由A、T、C、G组成的字符串，代表碱基序列。

字符串长度 \( \leq 1000\)

Output Format

输出共一行，为两个碱基序列的相似程度。

Hint

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;
}