題目要求輸出以某個(gè)字符串為前綴的word的數(shù)目，建立字典樹(shù)之后就是個(gè)簡(jiǎn)單的查詢(xún)了，為了性能采用了靜態(tài)字典樹(shù)，由于不知道會(huì)有多少個(gè)單詞就猜了下感覺(jué)10w應(yīng)該夠了吧，提交上去access violation，明顯的越界訪(fǎng)問(wèn)，修改為20W一樣出錯(cuò)，后來(lái)火了，直接開(kāi)到50w過(guò)了，測(cè)試數(shù)據(jù)相當(dāng)狠呀。
不多說(shuō)了，參考代碼如下。
#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;
}
喜歡 
頂
難過(guò)
囧
圍觀
無(wú)聊
