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 閱讀(231)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構