shi_vam's blog

By shi_vam, history, 3 weeks ago,

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.

• -1

 » 3 weeks ago, # |   0 Auto comment: topic has been updated by shi_vam (previous revision, new revision, compare).
 » 3 weeks ago, # |   0 Auto comment: topic has been updated by shi_vam (previous revision, new revision, compare).