Atcoder dp contest- LCS problem

Revision en1, by shi_vam, 2024-07-16 02:18:34

https://atcoder.jp/contests/dp/tasks/dp_f

void solve(){ string s; string t; cin>>s; cin>>t; int n=s.length(); int m=t.length(); vector<vector>dp(n,vector(m)); int index1=-1; for(int i=0;i<m;i++){ if(s[0]==t[i]){ index1=i; break; } } if(index1!=-1){ for(int i=index1;i<m;i++){ dp[0][i]=1; } } int index2=-1;

for(int i=0;i<n;i++){
    if(t[0]==s[i]){
        index2=i;
        break;
}

}
if(index2!=-1){
    for(int i=index2;i<n;i++){
        dp[i][0]=1;
    }

}
for(int i=1;i<n;i++){
    for(int j=1;j<m;j++){

            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

        if(s[i]==t[j]){
            dp[i][j]=max(dp[i][j],1+dp[i-1][j-1]);
        }
    }
}

string ans="";

int x=n-1;
 int y=m-1;
 while(x>=0 && y>=0){
    if(s[x]==t[y]){
        ans+=s[x];
        x--;
        y--;

    }else{

        if(x>0 && y>0 && dp[x-1][y]>=dp[x][y-1]){
            x--;

        }else{
            y--;
        }
    }

 }
 if(s[0]==t[0]){
    ans+=s[0];
 }
 reverse(ans.begin(),ans.end());
 cout<<ans<<'\n';

}

int main(){ int t=1;

while(t--){
    solve();
}

}

In my above code,I am getting some wa.Can anybody help me with problem where am i getting wa.

Tags atcoder.jp, lcs, dp problem

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English shi_vam 2024-07-16 02:21:34 12
en2 English shi_vam 2024-07-16 02:19:00 6
en1 English shi_vam 2024-07-16 02:18:34 1629 Initial revision (published)