NYOJ 685文字列辞書ツリーを検索

文字列の検索
時間制限:
1000 ms|メモリ制限:
65535 KB
難易度:
3
説明
明ちゃんは変な文字列が書かれた紙をもらいました.彼はいくつかの文字列が何回現れたか知りたいと思っていますが、これらの文字列が多すぎて、彼はあなたに助けを求めています.あなたは彼を助けることができますか.入力文字には、すべての小文字、'@'、'+'が含まれます.
入力
1行目は整数T(T<=100)を含む.テストデータのグループ数を示します.
次に、各データの最初の行には2つの整数n,m(n,m<100000)が含まれており、それぞれn文字列が表示されています.明ちゃんはあなたにm回聞きます.
次のn行は、各行に15以下の文字列を含む.
次にm行で、各行に文字列が含まれ、明ちゃんがその列が現れる回数を尋ねることを示します.
しゅつりょく
各グループの明ちゃん質問数列が現れる回数を出力します.
サンプル入力

1
5 3
hello
it@is+so@easy
hello
ibelieveicanac
hello
hello
icannotacit
Giveup

サンプル出力

3
0
0

  ‘+’ ASCII  43，‘@’  64，      97-122  ，‘+’ ‘z’  80，              80     。

#include<stdio.h>
#include<string.h>
#include<stdlib.h> 
struct node
{
    int cnt;
    struct node *next[80]; /*80    */
};
struct node *root;/*     */
struct node* build() /*      */
{ 
    struct node *p=(node *)malloc(sizeof(node));  /*      */
    p->cnt=0; 
    for(int i=0;i<80;i++)
    {
        p->next[i]=NULL; /*          */
    }
    return p;
}
int insert(char*s)
{
    struct node *p=root;
    int len=strlen(s);
    for(int i=0;i<len;i++)
    {
        if(p->next[s[i]-'+']!=NULL)
             p=p->next[s[i]-'+'];
        else
        {
            p->next[s[i]-'+']=build();
            p=p->next[s[i]-'+'];
        }
    }
    return p->cnt++;
}
int search(char *s)
{
    int len=strlen(s);
    struct node *p=root;
    for(int i=0;i<len;i++)
    {
        if(p->next[s[i]-'+']!=NULL)
           p=p->next[s[i]-'+'];
        else return 0;
    }
    return p->cnt;
}
int main()
{
    int n,m,t,i;
    char s1[20],s2[20];
    scanf("%d",&t);
    while(t--)
    {
		root=build();/*     */
        scanf("%d%d",&n,&m);
        getchar();
        for(i=0;i<n;i++)
        {
            gets(s1);
            insert(s1);
        }
        for(i=0;i<m;i++)
        {
            gets(s2);
            printf("%d
",search(s2));
        }
    }
	return 0;
}
        
        

実はテンプレートを使っています.