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
Sample Output
交际する时必ずC++で交际して、G++で无限にメモリを爆発させます...
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;
}