Submission

Score: 100

User: SparkPun

Problemset: Dvaravati-LCS

Language: cpp

Time: 0.004 second

Submitted On: 2025-11-04 20:12:14

#include <bits/stdc++.h>
using namespace std;
int main(){
    string s1,s2;
    cin >> s1;
    cin >> s2;
    int dp[s1.size()+1][s2.size()+1];
    for(int i=0;i<=s1.size();i++){
        for(int j=0;j<=s2.size();j++){
            if(i==0 || j==0){
                dp[i][j]=0;
            }
            else if(s1[i-1]==s2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    int idx=dp[s1.size()][s2.size()];
    string lcs(idx,' ');
    int i=s1.size(),j=s2.size();
    while(i>0 && j>0){
        if(s1[i-1]==s2[j-1]){
            lcs[idx-1]=s1[i-1];
            i--;
            j--;
            idx--;
        }
        else if(dp[i-1][j] > dp[i][j-1])
            i--;
        else
            j--;
    }
    cout << lcs << endl;
    cout << lcs.size() << endl; 
    if(lcs.length()>min(s1.size(),s2.size())/2){
        cout << "y";
    }
    else{
        cout << "n";
    }
}