字典树。
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;
}
}