首页 > 代码库 > hdu2222
hdu2222
数组开小了,还是小了很多,注意数组里的是节点总数!
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<algorithm>#define maxn 500000+10using namespace std;int ch[maxn][26],fail[maxn],last[maxn],val[maxn],sz,root;int newnode(){ memset(ch[sz],0,sizeof(ch[sz])); val[sz] = 0; return sz++;}void init(){ sz =0; root = newnode();}int insert(char *str){ int len = strlen(str); int now = root; for(int i =0;i < len;i++) { int &tmp = ch[now][str[i]-‘a‘]; if(!tmp) { tmp =newnode(); } now = tmp; } val[now]++; return now;}void getfail(){ queue<int>q; fail[root] =root; for(int i =0;i< 26;i++) { int u =ch[root][i]; if(u) { fail[u] = 0; last[u] =0; q.push(u); } } while(!q.empty()) { int now = q.front(); q.pop(); for(int i =0;i < 26;i++) { int u = ch[now][i]; if(!u) { ch[now][i] = ch[fail[now]][i]; } else { fail[u]= ch[fail[now]][i]; last[u] = val[fail[u]]?fail[u]:last[fail[u]]; q.push(u); } } }}int query(char*str){ int len = strlen(str); int now = root; int ret =0; for(int i =0;i < len; i++) { now = ch[now][str[i] -‘a‘]; int tmp =now; while(tmp != root&&val[tmp]) { ret += val[tmp]; val[tmp] = 0; tmp =last[tmp]; } } return ret;}int main(){ char str[1000010]; int n,m; scanf("%d",&n); while(n--) { init(); scanf("%d",&m); for(int i =0;i< m;i++) { scanf("%s",str); insert(str); } getfail(); scanf("%s",str); printf("%d\n",query(str)); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。