Trie的简单应用。
在每个结点中，用sum_记录以这个结点及其祖先为前缀的单词数目，将单词插入trie时，顺带更新sum_。
以下是我的代码：
#include<iostream>
#include<string>
#include<cstdio>
using namespace std;
struct TreeNode
{
TreeNode()
{
sum_=0;
for(int i=0;i<26;i++)
son_[i]=NULL;
}
int sum_;
TreeNode *son_[26];
};
class Trie
{
public:
Trie()
{
father_=new TreeNode;
}
void Insert(const string &s)
{
TreeNode *p(father_);
for(int i=0;i<s.size();i++)
{
if(!p->son_[s[i]-'a'])
p->son_[s[i]-'a']=new TreeNode;
p=p->son_[s[i]-'a'];
p->sum_++;
}
}
int Query(const string &s)
{
TreeNode *p(father_);
for(int i=0;i<s.size();i++)
{
p=p->son_[s[i]-'a'];
if(!p)
return 0;
}
return p->sum_;
}
private:
TreeNode *father_;
};
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
string s;
Trie trie;
while(getline(cin,s) && !s.empty())
trie.Insert(s);
while(getline(cin,s) && !s.empty())
cout<<trie.Query(s)<<endl;
return 0;
}
posted on 2011-03-06 11:36
lee1r 阅读(223)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构