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

字典树。

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;

    }

}