字典树的两种实现
hdu1251 动态链表实现:
#include<stdio.h>#include<string.h>int g[1000000][26]={0}; char c='a'; int tot=1;int rank[1000000]={0};void initial(){ memset(g[1],0,sizeof(g[1])); tot=1;}void insert(char* s){ int i,j; for(i=1;*s;++s) { if( !g[i][*s-c] ) { i=g[i][*s-c]=++tot; rank[i]++; //计数时要格外注意。 memset(g[tot],0,sizeof(g[tot])); } else i=g[i][*s-c],rank[i]++; }}int query(char* s){ int i,j; for(j=1;*s;++s) { if( !g[j][*s-c]) return 0; j=g[j][*s-c]; } return rank[j];}int main(){ int i,j,k; char str[20]; initial(); while(gets(str),strlen(str)>0) insert(str); while(scanf("%s",str)!=EOF) printf("%d\n",query(str)); return 0;}