?? 1816 wild words 字典樹.txt
字號:
#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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -