题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1251
题意：给你多个字符串，求以某个字符串为前缀的字符串数量。
思路：简单的trie数应用，在trie的数据结构中增加一个存储到当前节点字符串出现的次数，在插入的过程中维护即可。
code：
#include <cstdio>
#include <cstring>
const int KIND = ;
struct TrieNode
{
int num; // 遍历到该结点形成的字符串出现的次数
TrieNode* next[KIND];
TrieNode()
{
num = ;
for (int i = ; i < KIND; ++i) next[i] = NULL;
}
}; TrieNode* root = NULL; void Insert(char* x)
{
TrieNode* temp = root;
if (root == NULL) // 预判
{
temp = new TrieNode();
root = temp;
}
int len = strlen(x);
for (int i = ; i < len; ++i)
{
int curr = x[i] - 'a';
if (temp->next[curr] != NULL) ++(temp->next[curr]->num); // 已经存在
else temp->next[curr] = new TrieNode(); // 不存在
temp = temp->next[curr];
}
} int Search(char* x)
{
int ret = ;
if (root == NULL) return ret; // 预判
TrieNode* temp = root;
int len = strlen(x);
for (int i = ; i < len; ++i)
{
int curr = x[i] - 'a';
if (temp->next[curr] == NULL) return ;
temp = temp->next[curr];
ret = temp->num;
}
return ret;
} void Release(TrieNode* root)
{
if (NULL == root) return;
for (int i = ; i < KIND; ++i)
{
if (root->next[i] != NULL)
Release(root->next[i]);
}
delete root;
root = NULL;
} int main()
{
char str[];
while (gets(str))
{
if (str[] == '\0')
{
while (gets(str))
printf("%d\n", Search(str));
}
else Insert(str);
}
Release(root);
return ;
}