字典树模板题.
ps: 数组要开大, 40w 左右才行, 不然疯狂 re
代码:
- #include<iostream>
- #include<algorithm>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- int root;
- int tot=1;
- int trie[400500][30];
- int cnt[400500];
- void init()// 最后清空, 节省时间
- {
- memset(trie,0,sizeof(trie));
- memset(cnt,0,sizeof(cnt));
- tot=1;//RE 有可能是这里的问题
- }
- void build_trie(char *s)
- {
- int len=strlen(s);
- root=0;
- for(int i=0;i<len;i++)
- {
- int id=s[i]-'a';
- if(!trie[root][id])
- trie[root][id]=++tot;
- root=trie[root][id];
- cnt[root]++;
- }
- }
- int query(char *s)
- {
- int len=strlen(s);
- root=0;
- for(int i=0;i<len;i++)
- {
- int id=s[i]-'a';
- if(!trie[root][id])
- return false;
- root=trie[root][id];
- }
- return cnt[root];
- }
- int main()
- {
- char s[105];
- char t[105];
- int ans=0;
- init();
- while(gets(s))
- {
- int x=strlen(s);
- if(x==0)
- break;
- build_trie(s);
- }
- while(gets(t))
- {
- int flag=query(t);
- printf("%d\n",flag);
- }
- }
来源: http://www.bubuko.com/infodetail-2733451.html