題目要求輸出以某個字符串為前綴的word的數(shù)目，建立字典樹之后就是個簡單的查詢了，為了性能采用了靜態(tài)字典樹，由于不知道會有多少個單詞就猜了下感覺10w應該夠了吧，提交上去access violation，明顯的越界訪問，修改為20W一樣出錯，后來火了，直接開到50w過了，測試數(shù)據(jù)相當狠呀。
不多說了，參考代碼如下。
#include <stdio.h>
#include <stdlib.h>
struct node
{
int cnt;
int childs[26];
};
int avail = 1;
int cur = 0;
struct node tree[500000];
char buf[15];
int main(void)
{
int i;
int root;
int index;
int flag;
/*freopen("in.txt", "r", stdin);*/
while (fgets(buf, 15, stdin) != NULL && buf[0] != '\n')
{
i = 0;
root = 0;
while (buf[i] != '\n')
{
index = buf[i]-'a';
if (tree[root].childs[index] == 0)
{
tree[root].childs[index] = avail++;
}
++tree[tree[root].childs[index]].cnt;
root = tree[root].childs[index];
++i;
}
}
while (fgets(buf, 15, stdin) != NULL && buf[0] != '\n')
{
i = 0;
root = 0;
flag = 1;
while (buf[i] != '\n')
{
index = buf[i] - 'a';
if (tree[root].childs[index] == 0)
{
flag = 0;
break;
}
root = tree[root].childs[index];
++i;
}
printf("%d\n", flag == 1 ? tree[root].cnt : 0);
}
return 0;
}
喜歡 
頂
難過
囧
圍觀
無聊
