數組開小了，還是小了很多，注意數組里的是節點總數！

#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #define maxn 500000+10 using 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; }

?

轉載于:https://www.cnblogs.com/DUANZ/p/3892221.html

總結

以上是生活随笔為你收集整理的hdu2222的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。