hdu4287 字典树

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#define maxn 10

struct trie

{

    trie *next[];

    int sum;

    int flag;

};

trie *root;

char way[][];

void init()

{

    root=(trie*)malloc(sizeof(trie));

    for(int i=;i<;i++)

        root->next[i]=NULL;

    root->flag=;

    root->sum=;

}

int check(char c)

{

    if(c>='a'&&c<='c')

        return ;

    if(c>='d'&&c<='f')

        return ;

    if(c>='g'&&c<='i')

        return ;

    if(c>='j'&&c<='l')

        return ;

    if(c>='m'&&c<='o')

        return ;

    if(c>='p'&&c<='s')

        return ;

    if(c>='t'&&c<='v')

        return ;

    return ;

}

void insert(char *s)

{

    int i,j,len=strlen(s);

    trie *p=root,*q;

    for(i=;i<len;i++)

    {

        int id=check(s[i]);

        if(p->next[id]==NULL)

        {

            q=(trie*)malloc(sizeof(trie));

            for(j=;j<;j++)

                q->next[j]=NULL;

            q->flag=q->sum=;

            p->next[id]=q;

        }

        p=p->next[id];

        p->sum++;

        if(i==len-)

            p->flag++;

    }

}

int find(char *s)

{

    trie *p=root;

    int i,j,len=strlen(s);

    for(i=;i<len;i++)

    {

        int id=s[i]-'';

        if(p->next[id]==NULL)

            return ;

        p=p->next[id];

    }

    return p->flag;

}

void freetrie(trie *root)

{

    int i,j;

    for(i=;i<;i++)

    {

        if(root->next[i]!=NULL)

            freetrie(root->next[i]);

    }

    free(root);

}

int main()

{

    int i,j,t,n,m;

    char s[maxn];

    scanf("%d",&t);

    while(t--)

    {

        init();

        scanf("%d %d",&n,&m);

        for(i=;i<n;i++)

            scanf("%s",way[i]);

        for(i=;i<m;i++)

        {

            scanf("%s",s);

            insert(s);

        }

        for(i=;i<n;i++)

        {

            printf("%d\n",find(way[i]));

        }

        freetrie(root);

    }

}