HDU 1251 统计难题(很基础的Trie)
/*一道很基础的Trie树的问题过了，不过200ms，使用静态数组实现可能效果更好一些*/#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>using namespace std;const int SonNum = 27;int T, N;struct Trie{Trie *next[SonNum];int num;Trie(){num = 0;memset(next, 0, sizeof(next));}};int flag;int ans;void build(char *s, Trie *root)//建树{int i;Trie *p = root;for(i = 0; s[i]; ++ i){int index = s[i] - 'a';if(p->next[index] == NULL) p->next[index] = new Trie();p = p->next[index];p ->num ++;}}void match(char *s, Trie *root)//匹配{Trie *p = root;int i;for(i = 0; s[i]; ++ i){int index = s[i] - 'a';if(p->next[index] == NULL){flag = 1;break;}else p = p->next[index];}ans = p->num;}void del(Trie *root)//回首内存{int i;for(i = 0; i < SonNum; ++ i)if(root->next[i])del(root->next[i]);delete(root);}int main(){//freopen("e://data.in", "r", stdin);Trie *root = new Trie();char s[15];while(1){gets(s);if(s[0] == 0) break;build(s, root);}while(gets(s)){flag = 0;match(s, root);if(flag) printf("0\n");elseprintf("%d\n", ans);}del(root);return 0;}