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<int>>dp(n,vector<int>(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.
↵
↵
'''↵
void solve(){↵
string s;↵
string t;↵
cin>>s;↵
cin>>t;↵
int n=s.length();↵
int m=t.length();↵
vector<vector<int>>dp(n,vector<int>(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.
