Re: 531 - Compromise - WA
Posted: Tue Sep 03, 2013 9:42 pm
You're printing a null character at the end of each line.
Code: Select all
removed, after acc...
Code: Select all
/*
Approach: Longest Common Subsequence
*/
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#include<stack>
#include<queue>
#define PI 3.14159265
#define M 1000000007
#define EPS 1e-9
#define ll long long int
using namespace std;
const int N = 1000005;
int a[3005][3005];
vector<string>v;
int main()
{
//freopen("input.txt","r",stdin);
string s0;
while(getline(cin,s0))
{
if(s0.size()==0)break;
//cout<<" fuck "<<endl;
string s1[105]="",s2[105]="",s;int len1=0,len2=0;
//int c=0;
v.clear();
for(int i=0;i<s0.size();i++)
{
if(s0=="#")break;
if(s0[i]==' ')
{
//cout<<s1[len1] <<" ";
len1++;continue;
}
s1[len1]+=s0[i];
//len1++;
}
//cout<<s1[len1] <<endl;
len1++;
while(1 && s0!="#")
{
//cout<<"fuck"<<endl;
getline(cin,s);
if(s=="#")break;
for(int i=0;i<s.size();i++)
{
if(s[i]==' ')
{
// cout<<s1[len1] <<" ";
len1++;continue;
}
s1[len1]+=s[i];
}
len1++;
}
//cout<<s1[0]<<endl;
while(1)
{
getline(cin,s);
if(s=="#" || s.size()==0)break;
//if(s.size()>0)
//cout<<"funm?"<<endl;
for(int i=0;i<s.size();i++)
{
// cout<<"fuck"<<endl;
if(s[i]==' ')
{
len2++;continue;
}
s2[len2]+=s[i];
}
len2++;
}
//cout<<s1[len1-1]<<" " <<s2[len2-1]<<endl;
for(int i=0;i<len1;i++)
{
a[i][0]=0;
}
for(int j=0;j<len2;j++)
{
a[0][j]=0;
}
for(int i=1;i<=len1;i++)
{
for(int j=1;j<=len2;j++)
{
if(s1[i-1]==s2[j-1])
{
a[i][j]=a[i-1][j-1]+1;
}
else
{
a[i][j]=max(a[i-1][j],a[i][j-1]);
}
}
}
int i=len1,j=len2;
//cout<<len1<<" k "<<len2<<endl;
while(i>0 &&& j>0)
{
// cout<<i<<endl;
if(a[i][j]==a[i-1][j])i--;
else if(a[i][j]==a[i][j-1])j--;
else
{
v.push_back(s1[i-1]);
i--;j--;
}
}
reverse(v.begin(),v.end());
if(v.size()>=1)
{
//cout<<v[0];
for(int i=0;i<v.size();i++)
{
cout<<v[i];
if(i!=v.size()-1)cout<<" ";
else
cout<<endl;
}
}
}
return 0;
}
Code: Select all
a b c d e
#
b c d e a
#
a b a a
#
a a
#
Code: Select all
b c d e
a a