【题解】Gym – 102307C Common Subsequence

Manuel thinks that Diego is his long lost brother. But Diego thinks Manuel is wrong, and to prove it, he got DNA samples from himself and Manuel. Now Diego has given you the DNA samples and it is your task to say whether they are brothers or not.

The DNA samples of Diego and Manuel are strings A and B, both have length n (1≤n≤10^5) and consist of only the characters 'A', 'T', 'G' and 'C'. If there is a common subsequence of A and B that has length greater than or equal to 0.99×n, then Diego and Manuel are brothers, in other case, they are not.

Input
The input consists of two lines with strings A and B, respectively.

Output
You should output a single line with "Long lost brothers D:" (without quotes) if Diego and Manuel are brothers, and "Not brothers :(" (without quotes) if they are not.

Examples
input
GAATTGCGTACAATGC
GAATTGCGTACAATGC

output
Long lost brothers D:

input
CCATAGAGAA
CGATAGAGAA

output
Not brothers :(

Note
A subsequence of a string X is any string that you can get by removing any number of characters from X.

A common subsequence of strings X and Y is a string that is a subsequence of both X and Y.

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100002
#define INF (1 << 30)
string a, b;
int len;
vector<int> dp;
vector<int> dp_lis;

int vec[4][MAXN];
int js[4] = {0};
//A->0
//T->1
//C->2
//G->3

int ans = 0;

void lis()
{
    dp_lis.resize(dp.size() + 1);
    int sz = dp.size();
    fill(dp_lis.begin(), dp_lis.end(), INF);
    //cout<<"jsdp:"<<jsdp<<endl;
    for (int i = 0; i < sz; ++i)
    {
        *lower_bound(dp_lis.begin(), dp_lis.end(), dp[i]) = dp[i];
    }
    ans = lower_bound(dp_lis.begin(), dp_lis.end(), INF) - dp_lis.begin();
}

void solve()
{
    int idx;
    for (int i = len - 1; i >= 0; --i)
    {
        if (b[i] == 'A')
            idx = 0;
        else if (b[i] == 'T')
            idx = 1;
        else if (b[i] == 'C')
            idx = 2;
        else if (b[i] == 'G')
            idx = 3;
        

        vec[idx][js[idx]++] = i;
    }
    for (int i = 0; i < len; ++i)
    {
        if (a[i] == 'A')
            idx = 0;
        else if (a[i] == 'T')
            idx = 1;
        else if (a[i] == 'C')
            idx = 2;
        else if (a[i] == 'G')
            idx = 3;
        

        int sz = js[idx];
        for (int j = 0; j < sz; ++j)
        {
            dp.emplace_back(vec[idx][j]);
        }
    }
    lis();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> a >> b;
    len = a.length();

    solve();
    //cout<<ans<<endl;
    if (double(ans) >= 0.99 * len)
        cout << "Long lost brothers D:" << endl;
    else
        cout << "Not brothers :(" << endl;
}

#include <bits/stdc++.h>
using namespace std;

#define MAXN 100005

int dp[MAXN / 100 + 5][MAXN / 100 + 5]; //对删除的字符数进行dp

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    string a, b;
    cin >> a >> b;

    int len = a.length();
    int mx = len / 100 + 1; //最多删除的字符的数量
    int ans=0;
    for (int i = 0; i <= mx; ++i)
    {
        for (int j = 0; j <= mx; ++j)
        {
            //i、j分别为a、b串删除的字符数量, dp[i][j]为当a删除i个字符， b删除j个字符时，LCS的最长长度
            while (i + dp[i][j] < len && j + dp[i][j] < len && a[i + dp[i][j]] == b[j + dp[i][j]])
                ++dp[i][j];
            
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
            dp[i][j+1] = max(dp[i][j+1], dp[i][j]);
            ans = max(ans, dp[i][j]);
        }
    }

    if(1.0*ans/(1.0*len)>=0.99)
        cout<<"Long lost brothers D:"<<endl;
    else cout<<"Not brothers :("<<endl;
}