题目没有给出具体的规模，因此没有用枚举。我的做法是维护一棵Trie，把01串按长度从大到小的次序插入，这样就可以在插入时判断是否为之前某个长度更大串的前缀。尽管如此，依然用了0.408s的时间，可能与用cin/cout输入输出有关。
以下是我的代码：
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
const int kMaxn(10007);
bool cmp(const string &sa,const string &sb)
{
return (sa.size()>sb.size() || (sa.size()==sb.size() && sa<sb));
}
struct TreeNode
{
TreeNode():left_(NULL),right_(NULL) {}
TreeNode *left_,*right_;
};
class Trie
{
public:
Trie()
{
father_=new TreeNode;
}
bool Insert(const string &s)
{
bool re(false);
TreeNode *p(father_);
for(int i=0;i<s.size();i++)
{
if(s[i]=='0' && !p->left_)
{
p->left_=new TreeNode;
if(i==s.size()-1)
re=true;
}
else if(s[i]=='1' && !p->right_)
{
p->right_=new TreeNode;
if(i==s.size()-1)
re=true;
}
if(s[i]=='0')
p=p->left_;
else
p=p->right_;
}
return re;
}
private:
TreeNode *father_;
};
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
int T(0);
string t;
while(cin>>t)
{
vector<string> r;
while(t!="9")
{
r.push_back(t);
cin>>t;
}
sort(r.begin(),r.end(),cmp);
Trie trie;
bool success(true);
for(vector<string>::iterator i=r.begin();i!=r.end();i++)
if(!trie.Insert(*i))
{
success=false;
break;
}
T++;
if(success)
cout<<"Set "<<T<<" is immediately decodable"<<endl;
else cout<<"Set "<<T<<" is not immediately decodable"<<endl;
}
return 0;
}
posted on 2011-04-07 20:07
lee1r 阅读(441)
评论(1) 编辑 收藏 引用 所属分类:
题目分类：字符串处理 、
题目分类：数据结构