此题很明显的AC自动机。。。
先介绍一个神奇的性质：如果我们将AC自动机的Fail指针全部反向，将得到一棵由Fail指针组成的Fail Tree。对于模式串i来说，它的最后一个字母在Fail Tree中的节点的后代的数量与该串在其它串中出现的次数相等。
然后我们得到一个离线算法：
将询问双关键字排序，在FailTree上做一次DFS，得到DFS序。za再用树状数组维护前缀和。
具体做法：扫描原串，遇到小写字母，将相应的DFS序的位置+1，遇到P询问，B将字母弹出。
由于这个题还有许多细节，详细请看代码：
#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<queue>using namespace std;const int MAXSIZE=26;const int MAXN=210000;struct Node{ int Flag; Node *Next[MAXSIZE],*Fail,*Fa; Node(){ Flag=0; memset(Next,0,sizeof(Next)); //Fail=0; Fa=0; }}*Rt,*Path[MAXN],e[MAXN];Node *C=&e[0];Node *New_Node(){ Node *p=++C; return p;}struct Ask{ int u,v,Num,Ans; void Input(){ scanf("%d%d",&v,&u); } void Init(int u_,int v_,int Num_){ u=u_; v=v_; Num=Num_; }}Data[MAXN];bool cmp(const Ask &a,const Ask &b){ return a.u<b.u||(a.u==b.u&&a.v<b.v);}bool cmp1(const Ask &a,const Ask &b){ return a.Num<b.Num;}struct GNode{ int v; GNode *Next;};struct Graph{ GNode *adj[MAXN]; GNode edge[MAXN]; GNode *Cnt1; Graph(){ memset(adj,0,sizeof(adj)); memset(edge,0,sizeof(edge)); Cnt1=&edge[0]; } int Size[MAXN],Dfn[MAXN],Cnt; void addedge(int u,int v){ GNode *p=++Cnt1; p->v=v; p->Next=adj[u]; adj[u]=p; } void DFS(int u){ Size[u]=1; Dfn[u]=++Cnt; for(GNode *p=adj[u];p;p=p->Next){ int v=p->v; if(Dfn[v]) continue; DFS(v); Size[u]+=Size[v]; } }}FTree;char Cmd[MAXN*10];int n,Len;void Build(){ queue<Node*> q; //Rt=new Node; q.push(Rt); while(!q.empty()){ Node *p=q.front(); q.pop(); for(int i=0;i<MAXSIZE;++i){ if(p->Next[i]){ Node *x=p->Fail; while(x){ if(x->Next[i]){ p->Next[i]->Fail=x->Next[i]; break; } x=x->Fail; } if(!x){ p->Next[i]->Fail=Rt; } x=p->Next[i]->Fail; FTree.addedge(p->Next[i]->Flag,x->Flag); FTree.addedge(x->Flag,p->Next[i]->Flag); q.push(p->Next[i]); } } } FTree.DFS(0);}char Que[MAXN];int F,R,Cnt,Pos[MAXN],wCnt,Orz;Node *Osu;void Insert(int L,int R,int Num){ Node *p=Osu; for(int i=L;i<=R;++i){ int Hehe=Que[i]-'a'; if(!p->Next[Hehe]){ p->Next[Hehe]=New_Node(); p->Next[Hehe]->Flag=++Cnt; p->Next[Hehe]->Fa=p; Path[Cnt]=p; } if(i==R){ Pos[Num]=p->Next[Hehe]->Flag; Osu=p->Next[Hehe]; } p=p->Next[Hehe]; } Orz=Orz+(R-L+1); //Osu=p->Fa;}int Tree[MAXN];void Add(int x,int Val){ while(x<=FTree.Cnt){ Tree[x]+=Val; x+=x&-x; }}int GetSum(int x){ int Ret=0; while(x){ Ret+=Tree[x]; x-=x&-x; } return Ret;}int ACnt=1;int main(){ //freopen("sample.in","r",stdin); //freopen("type1.in","r",stdin); Rt=New_Node(); scanf("%s",&Cmd[1]); Len=strlen(Cmd+1); //printf("%d\n",Len); Osu=Rt; //Osu->Fa=Rt; int Pre=0; for(int i=1;i<=Len;++i){ if(Cmd[i]>='a'&&Cmd[i]<='z'){ Que[R++]=Cmd[i]; } else{ if(Cmd[i]=='P'){ ++wCnt;// Insert(Pre,R-1,wCnt); //F=R=0; Pre=R; } else{ R--; Pre--; Osu=Osu->Fa; } } } /*if(F<R){ wCnt++; Insert(F,R-1,wCnt); }*/ //printf("%d\n",Orz); scanf("%d",&n); for(int i=1;i<=n;++i){ Data[i].Input(); Data[i].Init(Data[i].u,Data[i].v,i); //Quer.addedge(Data[i].u,Data[i].v); } Build(); sort(Data+1,Data+n+1,cmp); F=R=0; int Hehe=0; Pre=0; Osu=Rt; for(int i=1;i<=Len;++i){ if(Cmd[i]>='a'&&Cmd[i]<='z'){ Que[R++]=Cmd[i]; } else{ if(Cmd[i]=='P'){ ++Hehe; Node *p=Osu; for(int j=Pre;j<R;++j){ int N=Que[j]-'a'; if(p->Next[N]){ Add(FTree.Dfn[p->Next[N]->Flag],1); } p=p->Next[N]; } Osu=p; Pre=R; //for(int j=ACnt;j<=n;++j){ while(ACnt<=n){ if(Data[ACnt].u>Hehe) break; else if(Data[ACnt].u==Hehe){ int L=FTree.Dfn[Pos[Data[ACnt].v]],R=L+FTree.Size[Pos[Data[ACnt].v]]-1; //L++; Data[ACnt].Ans=GetSum(R)-GetSum(L-1); } ACnt++; } /*p=Rt; for(int j=F;j<R;++j){ int N=Que[j]-'a'; if(p->Next[N]) Add(FTree.Dfn[p->Next[N]->Flag],-1); p=p->Next[N]; }*/ } if(Cmd[i]=='B'){ R--; Pre--; Add(FTree.Dfn[Osu->Flag],-1); Osu=Osu->Fa; } } } sort(Data+1,Data+n+1,cmp1); for(int i=1;i<=n;++i) printf("%d\n",Data[i].Ans);return 0;}
转载于:https://www.cnblogs.com/Return-0/archive/2013/04/18/3028742.html
相关资源：DirectX修复工具V4.0增强版