HDu 1251辞書ツリー

2228 ワード

統計上の課題
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others) Total Submission(s): 24535    Accepted Submission(s): 10139
Problem Description
Ignatiusは最近、ある文字列を接頭辞とする単語の数(単語自体も自分の接頭辞)を統計するように要求された.
 
Input
入力データの第1部は1枚の単語表で、1行ごとに1つの単語、単語の長さは10を超えないで、それらは先生がIgnatiusに渡して統計した単語を代表して、1つの空行は単語表の終わりを代表します.第2部は一連の質問で、各行は1つの質問で、各質問はすべて1つの文字列です.
注意:本題はテストデータのセットだけで、ファイルが終わるまで処理します.
 
Output
各質問に対して、その文字列を接頭辞とする単語の数を与える.
 
Sample Input

    
    
    
    
banana band bee absolute acm ba b band abc

 
Sample Output

    
    
    
    
2 3 1 0

 
交际する时必ずC++で交际して、G++で无限にメモリを爆発させます...
#include<iostream>
#include<set>
#include<map>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
struct trie
{
    trie *Next[27];
    int cnt;
    trie()//   
    {
        cnt = 0;
        memset(Next, 0, sizeof(Next));
    }
};
trie *root;
void init(char *str)
{
    int i;
    trie *p=root;
    for(i=0; str[i]; i++)
    {
        int id = str[i] - 'a';
        if(p->Next[id] == NULL)//     ,         
        {
            p->Next[id] = new trie;
            p = p->Next[id];
            p->cnt = 1;
        }
        else
        {
            p = p->Next[id];
            p->cnt++;//   +1
        }
    }
}
int finde(char *str)
{
    int i;
    trie *p=root;
    for(i=0; str[i]; i++)
    {
        int id=str[i]-'a';
        p=p->Next[id];
        if(p==NULL) return 0;//         
    }
    return p->cnt;//    
}
int main()
{
    char str[15];
    root = new trie;
    while(gets(str), str[0] != '\0')
    {
        init(str);//    
    }
    while(gets(str) != NULL)
    {
        printf("%d
", finde(str)); } return 0; }