#include <iostream> #include <cstring> #include <cstdlib> #include <algorithm> #include <cstring> #include <string.h> #include <stdio.h> using namespace std; const int CHARSET = 27, BASE = 'a', maxnode = 1000000; int cnt[maxnode];//保存从字典树根节点到某个节点有多少前缀. inline int idx(char x) { return x-BASE; } //Accepted 1251 78MS 43788K 1612 B G++ Achiberx struct Trie { int tot, root, child[maxnode][CHARSET]; bool flag[maxnode]; Trie () { //构造函数. memset(child[1], 0, sizeof(child[1])); memset(cnt, 0, sizeof(cnt)); flag[1] = false; root = tot = 1; } void Insert(const char *str) { int *cur = &root; for(const char *p = str; *p; ++p) { int id = idx(*p); //单词对应的数字. cur = &child[*cur][id]; if(*cur == 0) { //如果这还保存单词. *cur = ++tot; memset(child[tot], 0, sizeof(child[tot])); flag[tot] = false; } cnt[*cur]++;//每一个*cur标志着从根节点到此节点的唯一的路径. } flag[*cur] = true; } int query(const char *str) { int *cur = &root; for(const char *p = str; *p && *cur; ++p) { int id = idx(*p); cur = &child[*cur][id]; } return cnt[*cur]; } }; Trie tmp; int main() { char ch[15]; char *p = ch; while(gets(p) && (strlen(p)!=0)) { tmp.Insert(p); } while(gets(p) && (strlen(p)!=0)) { int res = tmp.query(p); printf("%d\n", res); } return 0; }