trie 内存池实现

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

const int N = 10000*20 + 10;  //单词个*长度+多开几个空间

struct NODE
{
  int flag;  //标记一个单词是否存在
  int son[26];
}trie[N];

int total = 1; //树的长度
void init()
{
 memset(trie,0xff,sizeof(trie));
}

void insert(char* str)
{
 int p=0,k=0;
 while(str[k])
 {
   int v=str[k]-'a';
   if(trie[p].son[v]==-1)
    trie[p].son[v]=total++;  //mempool
   p=trie[p].son[v];
   k++;
 }
 trie[p].flag=1;
}

int cur;  //控制输出单词个数
char ans[50];
void dfs(int k,int p)
{
 if(cur>=8)  return;
 if(trie[p].flag!=-1)  //单词存在
 {
   ans[k]=0;  //'\0'
   if(cur==0) printf("%s",ans);
   else   printf(" %s",ans);
   cur++;
 }
 for(int i=0;i<26;++i)
 {
   if(trie[p].son[i]!=-1)
   {
     ans[k] = i +'a';
     dfs(k+1,trie[p].son[i]);
   }
 }
 return ;
}

void find(char* str)
{
 int p=0,k=0;
 while(str[k] && p!=-1)
 {
   p = trie[p].son[str[k]-'a'];
   k++;
 }
 if(p==-1) //str这个没出现过,短路
 {
   printf("%s\n",str);
   return;
 }
 cur = 0;
 for(int i=0;i   ans[i]=str[i];
 dfs(k,p);
 printf("\n");
}

int main()
{

 #ifdef LOCAL
 freopen("data.in","r",stdin);
 freopen("data.out","w",stdout);
 #endif
 
 init();
 int i,n;
 char str[50];
 scanf("%d",&n);
 for(i=0;i {
  scanf("%s",str);
  insert(str);
 }
 int q;
 scanf("%d",&q);
 while(q--)
 {
   scanf("%s",str);
   find(str);
 }
 return 0;
}