首先比较明显的是我们可以将字符串组建立ac自动机，那么对于询问s1字符串在s2字符串中出现的次数，就是在以s1结尾为根的fail tree中，子树有多少个节点是s2的节点，这样我们处理fail tree的dfs序，然后用BIT维护，但是如果只是在线处理询问的话会tle，因为每个询问需要将节点的每一位在BIT中都修改，那么我们就浪费了好多性质，因为对于好多字符串拥有较长的LCP，那么我们可以模拟建trie的过程在自动机上跑，每遇到一个添加的字符，就解决所有询问为某字符串在该字符串中出现的次数，这样就可以了。
/************************************************************** Problem: 2434 User: BLADEVIL Language: C++ Result: Accepted Time:852 ms Memory:39128 kb ****************************************************************/ //By BLADEVIL #include <cstdio> #include <cstring> #define maxn 200010 using namespace std; struct node{ int cnt,last,left,right; node *child[30],*fail,*father; node(){ cnt=last=left=right=0; fail=father=NULL; memset(child,0,sizeof child); } }nodepool[maxn],*totnode,*root,*que[maxn],*adr[maxn],*other[maxn],*adrans[maxn]; char c[maxn]; int len,tot,l,sum; int pre[maxn],bit[maxn]; int ll,preans[maxn],otherans[maxn],lastans[maxn],sizeans[maxn]; int ans[maxn]; void add(int x,int y){ while (x<=sum){ bit[x]+=y; x+=x&(-x); } } int ask(int x){ int ans=0; while (x){ ans+=bit[x]; x-=x&(-x); } return ans; } void connect(node *x,node *y){ pre[++l]=x->last; x->last=l; other[l]=y; //printf("%d %d\n",x,y); } void connectans(int x,int y,int z){ preans[++l]=lastans[x]; lastans[x]=l; otherans[l]=y; sizeans[l]=z; } void build_trie(){ totnode=nodepool; root=totnode++; scanf("%s",&c); len=strlen(c); node *t=root; for (int i=0;i<len;i++){ if (c[i]=='P') adrans[++tot]=t; else if (c[i]=='B') t=t->father; else { if (!t->child[c[i]-'a']) t->child[c[i]-'a']=totnode++,t->child[c[i]-'a']->father=t; t=t->child[c[i]-'a']; adr[i]=t; }; //printf("%d ",t); } //printf("\n"); //for (int i=0;i<len;i++) printf("%d ",adr[i]); //for (node *i=nodepool;i!=totnode;i++) printf("%d %d\n",i,i->father); } void build_ac(){ int h=0,t=1; que[1]=root; root->fail=root; for (int i=0;i<26;i++) if (!root->child[i]) root->child[i]=root; while (h<t){ node *v=que[++h]; for (int i=0;i<26;i++) if (v->child[i]&&v->child[i]!=root){ que[++t]=v->child[i]; node *u=v->fail; que[t]->fail=u->child[i]!=que[t]?u->child[i]:root; } else v->child[i]=v->fail->child[i]; } //for (int i=1;i<=t;i++) printf("%d %d ",que[i],que[i]->fail); printf("\n"); //for (int i=1;i<=tot;i++) printf("%d ",adr[i]); printf("\n"); } void dfs(node *x,node *fa){ //printf("%d %d %d\n",x,fa,sum); x->left=++sum; for (int p=x->last;p;p=pre[p]){ if (other[p]==fa) continue; dfs(other[p],x); } x->right=sum; } /*void work(){ for (node *i=nodepool;i!=totnode;i++) if (i!=root) connect(i->fail,i); dfs(root,NULL); //for (node *i=nodepool;i!=totnode;i++) printf("%d %d %d %d\n",i,i->left,i->right,i->father); int m; scanf("%d",&m); while (m--){ int x,y; scanf("%d %d",&x,&y); for (node *i=adr[y];i!=root;i=i->father) add(i->left,1);//printf("%d ",i->left); //printf("%d %d",adr[x]->left,adr[x]->right); //printf("%d ",ask(adr[x]->right)); printf("%d\n",ask(adr[x]->right)-ask(adr[x]->left-1)); for (node *i=adr[y];i!=root;i=i->father) add(i->left,-1); } }*/ void work(){ for (node *i=nodepool;i!=totnode;i++) if (i!=root) connect(i->fail,i); dfs(root,NULL); int m; scanf("%d",&m); for (int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); connectans(y,x,i); } int stack[maxn],tot=0,ansy=0; memset(stack,0,sizeof stack); for (int i=0;i<len;i++){ if (c[i]=='P'){ ansy++; for (int p=lastans[ansy];p;p=preans[p]){ ans[sizeans[p]]=ask(adrans[otherans[p]]->right)-ask(adrans[otherans[p]]->left-1); } } else if (c[i]=='B') { add(adr[stack[tot--]]->left,-1); } else { stack[++tot]=i; add(adr[i]->left,1); } } for (int i=1;i<=m;i++) printf("%d\n",ans[i]); } int main(){ build_trie(); build_ac(); work(); return 0; }
