本文共 3956 字，大约阅读时间需要 13 分钟。
AC自动机。
首先第1行的输入就是让我们建AC自动机。。。。。。（提示好大）
记第i个字符串在AC自动机里面的点编号为pos[i]。
其实询问就是：对于在AC自动机里pos[y]到根的路径上的所有结点，有多少个在fail-tree中在以pos[x]为根的子树中。
我们可以先在fail-tree中DFS，求出每个点i的DFS序idx[i]，子树中最小的DFS序l[i]和子树中最大DFS序r[i]，并建立树状数组。
然后在AC自动机里DFS，访问点i就在idx[i]位置+1，离开点i就在idx[i]位置-1,这样就是维护了点i到根的路径上的所有结点。
然后在树状数组里询问即可。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include //#include 适用于CF,UOJ，但不适用于poj using namespace std;typedef long long LL;typedef double DB;typedef pair PII;typedef complex CP;#define mmst(a,v) memset(a,v,sizeof(a))#define mmcy(a,b) memcpy(a,b,sizeof(a))#define re(i,a,b) for(i=a;i<=b;i++)#define red(i,a,b) for(i=a;i>=b;i--)#define fi first#define se second#define m_p(a,b) make_pair(a,b)#define SF scanf#define PF printf#define two(k) (1<<(k))template inline T sqr(T x){ return x*x;}template inline void upmin(T &t,T tmp){ if(t>tmp)t=tmp;}template inline void upmax(T &t,T tmp){ if(t 0)?1:-1;}const DB Pi=acos(-1.0);inline int gint() { int res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; }inline LL gll() { LL res=0;bool neg=0;char z; for(z=getchar();z!=EOF && z!='-' && !isdigit(z);z=getchar()); if(z==EOF)return 0; if(z=='-'){neg=1;z=getchar();} for(;z!=EOF && isdigit(z);res=res*10+z-'0',z=getchar()); return (neg)?-res:res; }const int maxN=100000;const int maxM=100000;const int maxlen=100000;int N,M;char s[maxlen+100];int pos[maxN+100];int now,first[maxlen+100];struct Tedge{ int v,next;}edge[maxlen+100];inline void addedge(int u,int v) { now++; edge[now].v=v; edge[now].next=first[u]; first[u]=now; }int cnt,fa[maxlen+100],fail[maxlen+100],ch[maxlen+100][30];int head,tail,que[maxlen+100];inline void build() { int i,p; cnt=p=1; fa[1]=0; int len=strlen(s+1); re(i,1,len) if(s[i]=='B') p=fa[p]; else if(s[i]=='P') pos[++N]=p; else { if(!ch[p][s[i]-'a'])ch[p][s[i]-'a']=++cnt,fa[cnt]=p; p=ch[p][s[i]-'a']; } mmst(first,-1);now=-1; fail[que[head=tail=1]=1]=1; while(head<=tail) { int u=que[head++]; re(i,0,25)if(ch[u][i]) { int v=ch[u][i]; if(u==1) fail[que[++tail]=v]=1; else { int temp=fail[u]; while(temp!=1 && !ch[temp][i])temp=fail[temp]; if(ch[temp][i])temp=ch[temp][i]; fail[que[++tail]=v]=temp; } addedge(fail[v],v); } } }int ge,idx[maxlen+100],l[maxlen+100],r[maxlen+100];int top,sta[maxlen+100],last[maxlen+100];inline void DFS1() { idx[sta[top=1]=1]=ge=1; last[top]=first[1]; while(top>=1) { int u=sta[top],i=last[top],v; for(v=edge[i].v;i!=-1;i=edge[i].next,v=edge[i].v) { idx[sta[++top]=v]=++ge; last[top]=first[v]; last[top-1]=edge[i].next; break; } if(i==-1) { l[u]=r[u]=idx[u]; for(i=first[u],v=edge[i].v;i!=-1;i=edge[i].next,v=edge[i].v)upmin(l[u],l[v]),upmax(r[u],r[v]); top--; } } }#define lowbit(a) ((a)&(-(a)))int tree[maxlen+100];inline void update(int a,int v){ for(;a<=cnt;a+=lowbit(a))tree[a]+=v;}inline int ask(int l,int r) { int res=0; for(;r>=1;r-=lowbit(r))res+=tree[r]; for(l--;l>=1;l-=lowbit(l))res-=tree[l]; return res; }vector Q[maxlen+100];int ans[maxM+100];inline void DFS2() { sta[top=1]=1; last[top]=0; while(top>=1) { int u=sta[top],i=last[top],v,j; for(v=ch[u][i];i<26;i++,v=ch[u][i])if(v) { sta[++top]=v; last[top]=0; last[top-1]=i+1; update(idx[v],1); re(j,0,int(Q[v].size())-1) { int x=Q[v][j].fi,w=Q[v][j].se; ans[w]=ask(l[x],r[x]); } break; } if(i==26)update(idx[u],-1),top--; } }int main() { freopen("type.in","r",stdin); freopen("type.out","w",stdout); int i; scanf("%s\n",s+1); build(); M=gint(); re(i,1,M) { int x=gint(),y=gint(); Q[pos[y]].push_back(PII(pos[x],i)); } DFS1(); DFS2(); re(i,1,M)PF("%d\n",ans[i]); }
转载于:https://www.cnblogs.com/maijing/p/4698989.html
