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ǎ崽 阅读(880)
评论(3) 编辑 收藏 引用