HDU 4787 GRE Words Revenge

Description

　　Now Coach Pang is preparing for the Graduate Record Examinations as George did in 2011. At each day, Coach Pang can:
　　 "+w": learn a word w
　　 "?p": read a paragraph p, and count the number of learnt words. Formally speaking, count the number of substrings of p which is a learnt words.
　　Given the records of N days, help Coach Pang to find the count. For convenience, the characters occured in the words and paragraphs are only '0' and '1'.
　
　

Solution

这题网上大部分题解都是错的，只能说数据太水
首先这题用到AC自动机，如果暴力做每一组询问需要getfail一次，但是这样做也能AC.
考虑合并，我们建立两个AC自动机，保证其中一个大小\(<\sqrt{n}\) 每一次对小的进行getfail，复杂度只有\(O(\sqrt{n})\)，如果小的 \(size\) 达到了 \(\sqrt{n}\)，考虑暴力合并，复杂度 \(O(\sqrt{n})\)
注意一个细节，一个单词只能学习一次，所以每加一次需要判断之前是否存在，网上大部分都没有做这个

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <queue> #include <cmath> #define RG register #define il inline #define iter iterator #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; const int N=100005,M=600005; int m,kase=0,ans=0,B=100,root=0;char s[M*10]; queue<int>q; struct Ac{int size,ch[M][2],fail[M],val[M];int newnode(){size++;ch[size][0]=ch[size][1]=0;fail[size]=0;val[size]=0;return size;}void clear(){size=-1;newnode();}void ins(char *S){int x,len=strlen(s),p=root;for(int i=1;i<len;i++){x=S[i]-'0';if(ch[p][x])p=ch[p][x];else ch[p][x]=newnode(),p=ch[p][x];}val[p]|=1;}void getfail(){while(!q.empty())q.pop();q.push(root);int x,u,v;while(!q.empty()){x=q.front();q.pop();for(int i=0;i<=1;i++){if(!ch[x][i])continue;u=fail[x];while(u && !ch[u][i])u=fail[u];if(ch[u][i] && ch[u][i]!=ch[x][i])fail[ch[x][i]]=ch[u][i];v=ch[x][i];q.push(v);}}}int query(char *S){int x,len=strlen(S),p=root,ret=0,u;for(int i=1;i<len;i++){x=S[i]-'0';while(p && !ch[p][x])p=fail[p];p=ch[p][x];u=p;while(u)ret+=val[u],u=fail[u];}return ret;}bool check(char *S){int len=strlen(S),x,p=root;for(int i=1;i<len;i++){x=S[i]-'0';if(!ch[p][x])return false;p=ch[p][x];}return val[p];} }A,C; void dfs(int art,int crt){int x;for(int i=0;i<=1;i++)if(C.ch[crt][i]){if(!A.ch[art][i])A.ch[art][i]=A.newnode();x=A.ch[art][i];A.val[x]|=C.val[C.ch[crt][i]];dfs(x,C.ch[crt][i]);} } char b[N]; void Moveit(){int k=ans,len=strlen(s),p=1;k%=(len-1);for(int i=1;i<=k;i++)b[i]=s[i];for(int i=1;k<len-1;i++)s[i]=s[++k];for(int i=len-(ans%(len-1));i<len;i++)s[i]=b[p++]; } void work() {printf("Case #%d:\n",++kase);scanf("%d",&m);A.clear();C.clear();ans=0;while(m--){scanf("%s",s);Moveit();if(s[0]=='+'){if(A.check(s) || C.check(s))continue;C.ins(s);if(C.size>B){dfs(0,0);A.getfail();C.clear();}else C.getfail();}else ans=A.query(s)+C.query(s),printf("%d\n",ans);} }int main() {int T;cin>>T;while(T--)work();return 0; }

转载于:https://www.cnblogs.com/Yuzao/p/7661370.html

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的HDU 4787 GRE Words Revenge的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。