统计难题
p
| Time Limit: 2000MS | Memory Limit: 65535KB | 64bit IO Format: %I64d & %I64u |
[Submit]
Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana
band
bee
absolute
acm
ba
b
band
abc
Sample Output
2
3
1
0
题意很简单，字典树，基本都过了
代码：（不是我做的，队长做的）
C语言: 临时自用代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef
struct
node
{
struct
node
*
num
[
26
];
int
n;
} lnode , * link;
link
root;
link
create()
{
link
c;
int
i;
c
=(
link)
malloc(
sizeof(
lnode));
for(
i
=
0;
i
<
26;
i
++)
c
->
num
[
i
]
=
NULL;
c
->n
=
0;
return
c;
}
void
build(
char
a
[])
{
int
i
,
j;
link
cur
,
next;
j
=
strlen(
a);
cur
=
root;
for(
i
=
0;
i
<
j;
i
++)
{
if(
cur
->
num
[
a
[
i
]
-
'a'
]
!=
NULL)
cur
=
cur
->
num
[
a
[
i
]
-
'a'
];
else
{
next
=
create();
cur
->
num
[
a
[
i
]
-
'a'
]
=
next;
cur
=
next;
}
cur
->n
++;
}
}
int
look(
char
a
[])
{
int
i
,
j;
link
cur;
cur
=
root;
j
=
strlen(
a);
i
=
0;
for( i = 0; i < j; i ++)
if(
cur
->
num
[
a
[
i
]
-
'a'
]
==
NULL)
return
0;
else
cur
=
cur
->
num
[
a
[
i
]
-
'a'
];
return
cur
->n;
}
int
main()
{
char
a
[
20
];
#include<string.h>
#include<stdlib.h>
typedef
{
} lnode , * link;
link
link
{
}
void
{
}
int
{
for( i = 0; i < j; i ++)
}
int
{