http://acm.hdu.edu.cn/showproblem.php?pid=1251
#include<stdio.h>
struct tree
{
bool isword;
int child[26],cnt;
}T[1000001];
char word[11];
int L = 1,ans;//樹的總長
void Ins(char *a,int k,int idx)//k代表單詞長度，也是深度，idx代表樹的ID
{
if(!a[k])//這個單詞建完
return ;
if(T[idx].child[a[k] - 'a'])//找到這個單詞，繼續往下找
{
T[ T[idx].child[ a[k] -'a'] ].cnt ++ ;
Ins(a,k+1,T[idx].child[a[k]-'a']);
}
else
{
T[idx].child[a[k]-'a'] = ++L;//樹的總長++
T[L].isword = false;
T[L].cnt ++;
Ins(a,k+1,L);
}
}
void find(char *a ,int k,int idx)
{
if(!a[k])
{
ans = T[idx].cnt;//全部找完，返回
return ;
}
if(T[idx].child[a[k]-'a'] == 0)//找不到字母了，一定不是前綴
return ;
find(a,k+1,T[idx].child[a[k]-'a']);//繼續找下一個字母
}
int main()
{
T[1].isword = false;
while (gets(word),word[0])
Ins(word,0,1);
while (gets(word))
{
ans = 0;
find(word,0,1);
printf("%d\n",ans);
}
return 0;
}
posted on 2009-02-10 13:32
shǎ崽 閱讀(884)
評論(3) 編輯 收藏 引用