题解:
好题。
一个讲得很详细的题解:http://blog.csdn.net/huzecong/article/details/7769988
思路:这题的想法有点神啊....
先构建AC自动机,然后怎么判断一个串b是a的子串呢?用fail指针就可以了。如果a串中有节点可以通过fail指针走到b的终止节点,那么b就在a中出现过。有n个节点可以走到b,那么b就出现过n次。
现在就有一个暴力的想法,枚举a串的每个节点的fail看是否能到b,但是这是显然会T的。
然后我们可以倒过来想,把fail指针反向,建一棵fail树,对于b串,统计子树中有多少个a串的节点即可。
子树的节点的dfs序是相连的。
这样我们就可以用树状数组维护一下就好了。
#include<iostream> #include<cstring> #include<cstdio> #define maxn 100005 using namespace std; char s[maxn]; int son[maxn][26],fail[maxn],sum[maxn],lis[maxn]; int pre[maxn],now[maxn],v[maxn],fa[maxn]; int ppre[maxn],nnow[maxn],vv[maxn],t[maxn]; int ans[maxn],l[maxn],r[maxn]; int n,tot,cnt,id,len,T; void add(int x,int val) { for(int i=x;i<=T;i+=i&(-i))t[i]+=val; } int query(int x) { int sum=0; for(int i=x;i;i-=i&-i)sum+=t[i]; return sum; } void build() { scanf("%s",s+1); len=strlen(s+1); int p=0; tot=0; id=0; tot=0; for (int i=1; i<=len; i++) { if (s[i]=='P') sum[++id]=p; else if (s[i]=='B') p=fa[p]; else { int v=son[p][s[i]-'a']; if (!v) son[p][s[i]-'a']=++tot,fa[tot]=p; p=son[p][s[i]-'a']; } } //cout<<id<<endl; } void failed() { int head=0,tail=1; lis[1]=0; fail[0]=-1; while (head<tail) { int x=lis[++head]; for (int i=0; i<26; i++) { int v=son[x][i]; if (!v) continue; int p=fail[x]; while (p!=-1 && !son[p][i]) p=fail[p]; if (p==-1) fail[v]=0; else fail[v]=son[p][i]; lis[++tail]=v; } } for (int i=1; i<=tot; i++) { ppre[i]=nnow[fail[i]]; nnow[fail[i]]=i; vv[i]=i; //cout<<fail[i]<<" "<<i<<endl; } } void insert() { cin>>n; for (int i=1; i<=n; i++) { int x,y; cin>>x>>y; pre[i]=now[y]; now[y]=i; v[i]=x; } } void dfs(int x) { l[x]=++T; for (int i=nnow[x]; i; i=ppre[i]) { dfs(vv[i]); } r[x]=T; } void work() { int kk=0; add(l[0],1); int id=0; for (int i=1; i<=len; i++) { if (s[i]=='P') { ++id; for (int p=now[id]; p; p=pre[p]) { int t=sum[v[p]]; ans[p]=query(r[t])-query(l[t]-1); } } else if (s[i]=='B') add(l[kk],-1),kk=fa[kk]; else { kk=son[kk][s[i]-'a'];add(l[kk],1); } } } void print() { for (int i=1; i<=n; i++) printf("%d\n",ans[i]); } int main() { build(); failed(); insert(); dfs(0); work(); print(); } View Code