Submission

PPPPPPPPPP

Score: 100

User: Pera

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.003 second

Submitted On: 2025-04-01 17:19:55

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

string lcs(string str1, string str2, int m, int n) {
    vector<vector<int>> lcs_table(m+1, vector<int>(n+1));

    for (int i = 0; i <= m; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (i == 0 || j == 0) lcs_table[i][j] = 0;
            else if (str1[i-1] == str2[j-1]) lcs_table[i][j] = lcs_table[i-1][j-1] + 1;
            else lcs_table[i][j] = max(lcs_table[i-1][j], lcs_table[i][j-1]);
        }
    }   

    int index = lcs_table[m][n];
    string lcs;

    int i = m; int j = n;
    while (i > 0 && j > 0) {
        if (str1[i-1] == str2[j-1]) {
            lcs.push_back(str1[i-1]);
            i--;
            j--;
            index--;
        } else if (lcs_table[i-1][j] > lcs_table[i][j-1]) i--;
        else j--;
    }

    reverse(lcs.begin(), lcs.end());
    return lcs;

}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    string str1, str2;
    cin >> str1 >> str2;
    int m = str1.length(); int n = str2.length();
    string res = lcs(str1, str2, m, n);
    cout << res << '\n' << res.length() << '\n';

    if (res.length() > str1.length() / 2) cout << "y" << '\n';
    else cout << 'n' << '\n';
}