这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
题目传送门: http://acm.hdu.edu.cn/showproblem.php?pid=1251
标准的Trie树。 题目没有什么难度,直接套模版就OK了。
字典树资料: http://www.wutianqi.com/?p=1359 |
// Author: Tanky Woo
// www.wutianqi.com
// HDOJ 1251
// Trie
#include
using namespace std;
typedef struct Trie{
int v;
Trie *next[26];
}Trie;
Trie root;
void createTrie(char *str)
{
int len = strlen(str);
Trie *p = &root;, *q;
for(int i=0; inext[id] == NULL)
{
q = (Trie *)malloc(sizeof(root));
q->v = 1;
for(int j=0; j<26; ++j)
q->next[j] = NULL;
p->next[id] = q;
p = p->next[id];
}
else
{
p->next[id]->v++;
p = p->next[id];
}
}
}
int findTrie(char *str)
{
int len = strlen(str);
Trie *p = &root;
for(int i=0; inext[id];
if(p == NULL)
return 0;
}
return p->v;
}
int main()
{
//freopen("input.txt", "r", stdin);
char str[15];
int i;
for(i=0; i<26; ++i)
root.next[i] = NULL;
while(gets(str) && str[0]!='\0')
createTrie(str);
memset(str, 0, sizeof(str));
while(scanf("%s", str) != EOF)
{
int ans = findTrie(str);
printf("%d\n", ans);
}
return 0;
}