题目链接:http://poj.org/problem?id=1816
分析:就是Tire树
DFS的时候需要注意*的处理。
因为可能会有**出现。所以答案应该要去重。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 |
#include<cstdio>//BY:uncle-lu #include<cstring> #include<algorithm> using namespace std; struct node{ node* w[30]; char val; int num; }U[6000100],*Top=U,*root; node* ALLOC() { return new(Top++)node(); } int n,m; int ans[1000100]; int idx(const char x) { if(x=='*')return 27; if(x=='?')return 28; return x-'a'+1; } struct Tire { int V[1000100]; int F[1000100]; int sz; void init() { memset(V,0,sizeof(V)); memset(F,0,sizeof(F)); sz=0; return ; } void Insert(char* s,node* &x,const int sit) { if(!x){ x=ALLOC(); sz++; x->num=sz; memset(x->w,0x0,sizeof(x->w)); } if(!*s) { F[sit]=V[x->num]; V[x->num]=sit; return ; } Insert(s+1,x->w[idx(s[0])],sit); return ; } void Find(char* s,node* &x) { if(!*s) { int k=V[x->num]; while(k) { ans[0]++; ans[ans[0]]=k-1; k=F[k]; } } if(x->w[27]!=NULL) { int l=strlen(s); for(int i=0;i<=l;++i) { Find(s+i,x->w[27]); } } if(!*s)return ; if(x->w[28]!=NULL) { Find(s+1,x->w[28]); } if(x->w[idx(s[0])]!=NULL) { Find(s+1,x->w[idx(s[0])]); } return ; } }T; int main() { //freopen("./3.in","r",stdin); char s[100]; while(~scanf("%d%d",&n,&m)) { Top=U; root=ALLOC(); root->num=0; T.init(); for(int i=1;i<=n;++i) { scanf("%s",s+1); T.Insert(s+1,root,i); } for(int i=1;i<=m;++i) { ans[0]=0; scanf("%s",s+1); T.Find(s+1,root); if(ans[0]) { sort(ans+1,ans+1+ans[0]); ans[0]=unique(ans+1,ans+1+ans[0])-ans-1; printf("%d",ans[1]); for(int j=2;j<=ans[0];++j) { printf(" %d",ans[j]); } printf("\n"); } else printf("Not match\n"); } } //fclose(stdin); return 0; } |
还有就是指针技巧:
每次new的话就会跑的很慢。
所以我们应该开好。然后每次去调开好的空间。
Tire树没有回收。如果有回收。需要另开个指针回收。
反正就是些奇技淫巧。
