| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:线性时间能否做到?In Reply To:线性时间能否做到? Posted by:qiqilrq at 2007-04-14 14:22:59 #include<iostream>
#include<string>
using namespace std;
string a,b,c;
bool check(){
int i=0,j=0,k=0;
int alen=a.length(),blen=b.length(),clen=c.length();
if(a.at(alen-1)!=c.at(clen-1)&&b.at(blen-1)!=c.at(clen-1))return false;
while(k<clen){
if(i<alen&&j<blen&&c.at(k)==a.at(i)&&c.at(k)==b.at(j)){
int ti=i,tj=j,tk=k;
while(i<alen&&j<blen&&c.at(k)==a.at(i)&&c.at(k)==b.at(j)){
i++;j++;k++;
}
if(i<alen&&j<blen&&c.at(k)!=a.at(i)&&c.at(k)!=b.at(j)){
if(c.at(k)!=a.at(ti)&&c.at(k)!=b.at(tj)){
return false;
}else{
if(i<alen&&c.at(k)==a.at(i))i=ti;
else j=tj;
}
}else{
if(i<alen&&c.at(k)==a.at(i))j=tj;
else i=ti;
}
}else if(i<alen&&c.at(k)==a.at(i)){
i++;k++;
}else if(j<blen&&c.at(k)==b.at(j)){
j++;k++;
}else{
return false;
}
}
return (i+j)==k;
}
int main()
{
freopen("in.txt","r",stdin);
int t;
cin>>t;
int test=1;
while(t--){
cin>>a>>b>>c;
cout<<"Data set "<<test++<<": "<<(check()?"yes":"no")<<endl;
}
return 0;
}
这样写也不对~~不知道哪里错了
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator