字典树~
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 |
#include <cstdio> #include <cstring>using
namespace std;int cnt,n;char
s[12];struct
Node{int
sum; int
son[26];}trie[500000];void
insert(char
*s){ for(int
l=strlen(s),x=0,i=0;i<l;i++){ if(!trie[x].son[s[i]-‘a‘])trie[x].son[s[i]-‘a‘]=++cnt; x=trie[x].son[s[i]-‘a‘]; trie[x].sum++; }}int
find(char
*s){ for(int
l=strlen(s),x=0,i=0;i<l;i++){ if(!trie[x].son[s[i]-‘a‘])return
0; x=trie[x].son[s[i]-‘a‘]; if(i==l-1)return
trie[x].sum; }}int
main(){ while(gets(s)){ if(strlen(s)==0)break; insert(s); } while(gets(s))printf("%d\n",find(s)); return
0;} |
原文：http://www.cnblogs.com/forever97/p/3559382.html