心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
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 阅读(228) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理