HU 1251統計の難題の字典の木は裸で書きます
4156 ワード
HU 1251統計難問
Time Limit:2000 MS Memory Limit:65535 KB 64 bit IO Format:%I 64 d&%I 64 u Submit
Status
Practice
Description
Ignatiusは最近難しい問題に遭いました.先生は彼に多くの単語を渡しました.(小文字だけで構成されています.重複した単語は現れません.).今先生はある文字列を接頭語とする単語の数を統計してくださいと言いました.
Input
入力データの第一部は単语の表で、行ごとに一つの単语、単语の长さは10を超えないです.その代表は先生がIgnatiusに渡した単语で、一つの空行は単语の表の终わりを表します.
注意:この問題はテストデータのセットだけで、ファイルの最後まで処理します.
Output
各質問に対して、文字列をプレフィックスとする単語の数が与えられる.
Sample Input
bana band bee absoute acm
ba b band abc
Sample Output
2 3 1 0
クイズ:
辞書の木を叩くだけでいいです.
コード
Time Limit:2000 MS Memory Limit:65535 KB 64 bit IO Format:%I 64 d&%I 64 u Submit
Status
Practice
Description
Ignatiusは最近難しい問題に遭いました.先生は彼に多くの単語を渡しました.(小文字だけで構成されています.重複した単語は現れません.).今先生はある文字列を接頭語とする単語の数を統計してくださいと言いました.
Input
入力データの第一部は単语の表で、行ごとに一つの単语、単语の长さは10を超えないです.その代表は先生がIgnatiusに渡した単语で、一つの空行は単语の表の终わりを表します.
注意:この問題はテストデータのセットだけで、ファイルの最後まで処理します.
Output
各質問に対して、文字列をプレフィックスとする単語の数が与えられる.
Sample Input
bana band bee absoute acm
ba b band abc
Sample Output
2 3 1 0
クイズ:
辞書の木を叩くだけでいいです.
コード
#include
#include
#include
#include
using namespace std;
const int maxn = 500002;
int Next[maxn][27];
int word[maxn];
struct Tree
{
int L,root;
void init()
{
L = 0;
root = newnode();
}
int newnode()
{
for (int i = 0;i<27;i++)
Next[L][i] = -1;
word[L++]=0;
return L-1;
}
void insert(char *s)
{
int u = root;
int l = strlen(s);
for (int i = 0;iint c = s[i] - 'a';
if (Next[u][c] == -1)
Next[u][c] = newnode();
u = Next[u][c];
word[u]++;
}
}
int query(char *s)
{
int u = root;
int l = strlen(s);
for (int i = 0;iint c = s[i] - 'a';
if (Next[u][c] == -1)
return 0;
u=Next[u][c];
}
return word[u];
}
};
int main()
{
Tree tree;
tree.init();
char str[1001];
while (gets(str))
{
if (!strcmp(str,""))
break;
tree.insert(str);
}
char s[1001];
while (scanf("%s",s)!=EOF)
{
int count = tree.query(s);
printf("%d
",count);
}
}