1816 wild words 字典树.txt

NUAA ACM OJ源码

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include <vector>
#include <iterator>
#include <algorithm>
using namespace std;
#define PB push_back
#define PO pop_back
#define BG begin
#define ED end

//1816 Wild Words 字典树
#define NMAX 100005
typedef  struct tire
{
   struct tire *next[28];
   char date;
   int cnt;
   vector <int> has;
}*_tire;

int ans[NMAX];
int stack;

void init_tire(_tire root, char *string,int cixu)
{
    _tire s;
	int i;
    s=root;
    
    while(*string!='\0')
    {
       if(s->next[*string - 'a']==NULL)
       {	//不能用malloc，否则vector类型的has不能申请空间
          s->next[*string - 'a'] = (tire *)(new tire);//(_tire)malloc(sizeof(struct tire));
          (s->next[*string - 'a'])->date = *string;
		   (s->next[*string - 'a'])->cnt = 0;
          s = s->next[*string - 'a'];
          for(i=0;i<28;i++)
          {
              s->next[i] = NULL;
          }
       }
       else
       {
          s = s->next[*string - 'a'];
       }
       string++;
    }
    s->cnt=1;
    s->has.PB(cixu);
}

void print(_tire root, char *s, int i)
{
    int j;
    s[i] = root->date;

    if(root->cnt==1)
    {
        s[i+1] = '\0';
        puts(s);
    }
    
    for(j=0;j<28;j++)
    {
        if(root->next[j]!=NULL)
        {
           print(root->next[j],s,i+1);
        }
    }

}

void find(_tire root,char *key,int i,int len)
{
	int j,k;
    vector <int>::iterator vi;
//  此句保留，提醒自己错误：当字典中有the*,查the时，会立即返回，查不出the
//	if(root->cnt!=1 && key[i]=='\0' ) return;
//	注意i==len,当字典中有????,查he时，会出现key[4]='\0'(key[4]=key[3]=key[2]='\0'),这样会误查出he
	if(root->cnt==1 && key[i]=='\0' && i==len) 
	{
        for(vi=root->has.BG();vi!=root->has.ED();vi++) ans[++stack]=*vi;;
	}
	for(j=0;j<28;j++)
	{
		if(root->next[j]!=NULL)
        {
            if((root->next[j])->date==key[i])
			 find(root->next[j],key,i+1,len);
			if((root->next[j])->date=='|')
			{
                 for(k=i;k<=len;k++)
                 find(root->next[j],key,k,len);
            }
            if((root->next[j])->date=='{')
          		find(root->next[j],key,i+1,len);
		}
	}
}

bool cmp(int a,int b) {return a<b;}
int main()
{
    _tire root;
    int m,n,i,j,len;
    char s[265],ss[265];
    
    root = (_tire)malloc(sizeof(struct tire));
    for(i=0;i<28;i++)
    {
       root->next[i]=NULL;
    }
    scanf("%d %d",&n,&m);
    getchar();
    for(j=1;j<=n;j++)
    {
       gets(s);
       len=strlen(s);
       for(i=0;i<len;i++)
       {
         if(s[i]=='?') s[i]='{';
         if(s[i]=='*') s[i]='|';
       }
       init_tire(root,s,j-1);
    }
//    puts("\n依字典排序后：");
//    for(i=0;i<28;i++)
//    {
//       if(root->next[i] != NULL)
//       {
//          print(root->next[i],ss,0);
//       }
//    }
   for(j=1;j<=m;j++)
   {
     gets(s);
     len=strlen(s);
	 stack=0;
     find(root,s,0,len);
     if(0==stack)
     	printf("Not match\n");
	 else
	 {
		 sort(ans+1,ans+1+stack,cmp);
		 printf("%d ",ans[1]);
		 for(i=2;i<=stack;i++)
		 {
			 if(ans[i]!=ans[i-1])
			 printf("%d ",ans[i]);
		 }
		 printf("\n");
	 }
   }
//    system("pause");
    return 0;
}