注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

[The 2009 ACM-ICPC Asia Harbin Regional Contest]G.Fuzzy Google Suggest  

2012-04-08 17:17:58|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

字典树。

CODE:

#include <iostream>

#include <algorithm>

#include <string>

#include <cstring>

#include <cassert>

#include <sstream>

#include <map>

#include <vector>

#include <set>

using namespace std;

 

struct Trie

{

    Trie* f;

    Trie* c[26];

    int d;

};

Trie pool[4*1024*1024];

Trie* top=pool;

Trie* root;

#define f(x) ((x)-'a')

 

void calc(Trie* p,char* s,int d,set<Trie*>& get)

{

    if (p)

    {

       if (*s)

       {

           calc(p->c[f(*s)],s+1,d,get);

           if (d)

           {

              for (int i=0;i<26;i++)

                  calc(p->c[i],s,d-1,get);

              for (int i=0;i<26;i++)

                  calc(p,s+1,d-1,get);

              for (int i=0;i<26;i++)

                  calc(p->c[i],s+1,d-1,get);

           }

       }

       else get.insert(p);

    }

}

 

 

int main()

{

    root=top++;

    int n,m;

    cin>>n;

    for (int i=0;i<n;i++)

    {

       char db[16];

       cin>>db;

       Trie* p=root;

       char* s=db;

       while (*s)

       {

           if (!p->c[f(*s)]) top->f=p,p->c[f(*s)]=top++;

           p=p->c[f(*s)];

           p->d++;

           s++;

       }

    }

    cin>>m;

    for (int i=0;i<m;i++)

    {

       char s[1024];

       int d;

       cin>>s>>d;

       set<Trie*> get;

       calc(root,s,d,get);

       int answer=0;

       for (set<Trie*>::reverse_iterator it=get.rbegin();it!=get.rend();it++)

       {

           Trie* p=*it;

           int delta=p->d;

           while (p!=root)

           {

              p=p->f;

              set<Trie*>::iterator t=get.find(p);

              if (t!=get.end()) delta=0;

           }

           answer+=delta;

       }

       cout<<answer<<endl;

    }

}

 

  评论这张
 
阅读(1072)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018