字典树的两种实现

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;}