bzoj2434: [Noi2011]阿狸的打字机

本文主要是介绍bzoj2434: [Noi2011]阿狸的打字机，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：http://www.lydsy.com:808/JudgeOnline/problem.php?id=2434

一个讲得很详细的题解：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<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=100010;
using namespace std;
int m,len,num,preq[maxn],nowq[maxn],sonq[maxn],l[maxn],r[maxn],bit[maxn],pos[maxn],cnt,pre[maxn],now[maxn],son[maxn],ans[maxn];char s[maxn],ch;
void change(int x,int val){for (;x<=cnt;x+=x&-x) bit[x]+=val;}
int query(int x){int res=0;for (;x;x-=x&-x) res+=bit[x];return res;
}
void add(int a,int b){pre[++num]=now[a],now[a]=num,son[num]=b;}
void read(int &x){for (ch=getchar();!isdigit(ch);ch=getchar());for (x=0;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
}struct AC_DFA{int tot,ch[maxn][26],fail[maxn],q[maxn],fa[maxn],head,tail;void build(){int p=0,id=0;for (int i=0;i<len;i++)if (s[i]=='P') pos[++id]=p;else if (s[i]=='B') p=fa[p];else{if (!ch[p][s[i]-'a']) ch[p][s[i]-'a']=++tot,fa[tot]=p;p=ch[p][s[i]-'a'];}}void getfail(){head=0,q[tail=1]=0,fail[0]=-1;while (head!=tail){int x=q[++head];for (int i=0;i<26;i++)if (ch[x][i])q[++tail]=ch[x][i],fail[ch[x][i]]=x==0?0:ch[fail[x]][i];else ch[x][i]=x==0?0:ch[fail[x]][i];}}void dfs(int x){l[x]=++cnt;for (int y=now[x];y;y=pre[y])dfs(son[y]);r[x]=cnt;}void work(){int p=0,id=0;change(l[0],1);for (int i=0;i<len;i++)if (s[i]=='P'){id++;for (int y=nowq[id];y;y=preq[y]){int t=pos[sonq[y]];ans[y]=query(r[t])-query(l[t]-1);}}else if (s[i]=='B') change(l[p],-1),p=fa[p];else p=ch[p][s[i]-'a'],change(l[p],1);}
}T;int main(){scanf("%s%d",s,&m);len=strlen(s);for (int i=1,x,y;i<=m;i++){read(x),read(y);preq[i]=nowq[y],sonq[i]=x,nowq[y]=i;}T.build(),T.getfail();for (int i=1;i<=T.tot;i++) add(T.fail[i],i);T.dfs(0),T.work();for (int i=1;i<=m;i++) printf("%d\n",ans[i]);return 0;
}

这篇关于bzoj2434: [Noi2011]阿狸的打字机的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---