hdu2072 字典树

这题印象深刻,我刚接触acm时,以为这题是水题(因为是中文,又短),一直没做出。现再想想也是。可能也是我以前字符串掌握不好;

这题其实也可以用stl里的map写。这里我用字典树写的。其实这题算简单题了吧。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct trie
{
trie *next[];
int flag;//flag标记这里是否一个单词结束,也就是说到这里是否有一个单词;
};
trie *root;
void init()
{
int i;
root=(trie*)malloc(sizeof(trie));
for(i=;i<;i++)
{
root->next[i]=NULL;
}
root->flag=;
}
void insert(char *str)
{
trie *p=root,*q;
int i,j,len=strlen(str);
for(i=;i<len;i++)
{
int id=str[i]-'a';
if(p->next[id]==NULL)
{
q=(trie*)malloc(sizeof(trie));
for(j=;j<;j++)
q->next[j]=NULL;
q->flag=;
p->next[id]=q;
}
p=p->next[id];
if(i==len-)
p->flag=;
}
}
int query(char *str)
{
int i,len=strlen(str);
trie *p=root;
for(i=;i<len;i++)
{
int id=str[i]-'a';
if(p->next[id]==NULL)
return ;
else
{
p=p->next[id];
}
}
if(p->flag==)
return ;
return ;
}
int main()
{
int i,j,ans;
char str[],s[];
while(gets(str))
{
ans=;
init();
if(str[]=='#')break;
int len=strlen(str);
int num;
for(i=;i<len;i++)
{
num=;
for(j=i;j<len;j++)
{
if(str[j]==' ')
break;
s[num++]=str[j];//读取单词
}
i=j;
s[num]='\0';
//printf("%s ",s);
if(strcmp(s,"")!=&&query(s))//前面strcmp主要为了防止空格
{
insert(s);
ans++;
}
}
printf("%d\n",ans);
}
}
上一篇:对称加密算法 (DES、3DES、AES、RC)


下一篇:maven常见异常以及解决方法