首页 > 代码库 > HDU 1251 统计难题
HDU 1251 统计难题
字典树问题。
其实也可以用map水过去。但是想到我还要巩固……
唉,还是老老实实用字典树。不过 输入中间的 空行 卡了我一下,RE……
果断判断*str AC了。
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<queue> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 using namespace std; struct Trie { int word[410000][26]; int sz; int ex[4100000]; Trie() { sz=1; memset(word,0,sizeof(word)); memset(ex,0,sizeof(ex)); } void insert(char *s) { int u=0,c,len=strlen(s); for(int i=0;i<len;i++) { c=s[i]-'a'; if(!word[u][c]) { word[u][c]=sz++; } u=word[u][c]; ex[u]++; } } int search(char *s) { int u=0,c,len=strlen(s); for(int i=0;i<len;i++) { c=s[i]-'a'; if(word[u][c]) u=word[u][c]; else return 0; } return ex[u]; } }wo; int main() { char str[11]; while(gets(str),*str) wo.insert(str); while(scanf("%s",str)!=EOF) { int tmp=wo.search(str); printf("%d\n",tmp); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。