HDU 1251統計難問-辞書ツリー
1594 ワード
相互テーマリンクhttp://acm.hdu.edu.cn/showproblem.php?pid=1251
基礎辞書ツリー:
基礎辞書ツリー:
#include
#include
char s[15];
struct node
{
int cnt;
node *next[26];
void init() //
{
cnt=0;
for(int i=0;i<26;i++)
{
next[i]=NULL;
}
}
} ;
void insert(node *root,char *s)
{
node *p=root;
for(int i=0;s[i];i++)
{
int t=s[i]-'a';
if(p->next[t]==NULL)
{
p->next[t]=new node;
p=p->next[t];
p->init() ;
}
else
p=p->next[t];
p->cnt++;
}
}
int find(node *root, char *s)
{
node *p=root;
for(int i=0;s[i];i++)
{
int t=s[i]-'a';
p=p->next[t];
if(!p) return 0;
}
return p->cnt;
}
int main()
{
node *root=new node();
root->init() ;
while(gets(s)&&strlen(s))// !!!
{
insert(root,s);
}
while(gets(s))
{
printf("%d
",find(root,s));
}
return 0;
}
大神コードは、シンプルですが、タイムアウトしやすいので注意してください!#include
#include
#include