[NOI2011] 阿狸的打字机

题目描述

阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有 $28$ 个按键，分别印有 $26$ 个小写英文字母和 B、P 两个字母。经阿狸研究发现，这个打字机是这样工作的：

输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。
按一下印有 B 的按键，打字机凹槽中最后一个字母会消失。
按一下印有 P 的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。

例如，阿狸输入 aPaPBbP，纸上被打印的字符如下：

a
aa
ab

我们把纸上打印出来的字符串从 $1$ 开始顺序编号，一直到 $n$ 。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数 $(x, y)$ （其中 $1\leq x,y\leq n$ ），打字机会显示第 $x$ 个打印的字符串在第 $y$ 个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋，他想写个程序完成同样的功能，你能帮助他么？

题解

今天才发现以前学的的ac自动机是假的。
这道题我们直接按照按照last数组（fail的优化）往上跳，可以90point。
不过数据是真的水

inline void add(int x,int y,int id){++tot;to1[tot]=y; to2[tot]=id; nex[tot]=head[x]; head[x]=tot;
}
inline void add1(int x,int y){to[++hh]=y; ne[tot]=he[x]; he[x]=hh;  //ne也用的tot
}

这样居然可以90？？？

说说正解
先说说正确的ac自动机姿势

给你一个文本串 $S$ 和 $n$ 个模式串 $T_{1 \sim n}$ ，请你分别求出每个模式串 $T_i$ 在 $S$ 中出现的次数。

假设我们当前在ac自动机上走到now这个点，那么一个显然的想法就是沿着fail链往上跳，然后所有走到的点（字符串结尾）+1。

设 $f ai l [x] = y$
反过来想，如果我们将y连向x，那么这个关系将会构成一颗树，我们只需要将字符串到过的点打个标记，最后求一遍子树和即可。

#include<cstdio>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int N=2e6+5;
int ch[N][26],fa[N],now,cnt,l,n,c,val[N],mat[N];
char s[N];
int h,t,q[N],r,u,v,f[N];
int head[N],to[N],nex[N],tot,sum[N];
void ins(int x){now=0;fo(i,1,l){c=s[i]-'a';if (!ch[now][c]) ch[now][c]=++cnt;now=ch[now][c];}mat[x]=now;
}
void build(){h=t=0;fo(i,0,25) if (ch[0][i]) q[++t]=ch[0][i];while (h<t){r=q[++h];fo(i,0,25){u=ch[r][i];if (!u) {ch[r][i]=ch[f[r]][i];//与下一个代码有区别continue; }v=f[r];while (v && !ch[v][i]) v=f[v];f[u]=ch[v][i];q[++t]=u;}}
}
void add(int x,int y){to[++tot]=y; nex[tot]=head[x]; head[x]=tot;
}
void dfs(int x){for (int i=head[x];i;i=nex[i]){int v=to[i];dfs(v);sum[x]+=sum[v];}
}
int main(){
//	freopen("data.in","r",stdin);scanf("%d",&n);fo(i,1,n){scanf("%s",s+1);l=strlen(s+1);ins(i);}build();scanf("%s",s+1);l=strlen(s+1);now=0;fo(i,1,l) {c=s[i]-'a';now=ch[now][c];sum[now]++;}fo(i,1,cnt) add(f[i],i);dfs(0);fo(i,1,n) {printf("%d\n",sum[mat[i]]);}return 0;
}

那么这个题其实也差不多。
首先建好树后先得到dfs序，一个字树的dfs序肯定是一段连续的区间。我们只需要dfs的时候修改即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for (register int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int N=1e5+1000;
int ch[N][26];
char s[N];
int n,m,x,y,now,l,c,cnt;
int f[N],fa,val[N],sum;
int h,t,q[N],r,u,v,ans[N],d[N],Fa[N],wh[N],dep;
bool vis[N];
int to[N],ne[N],head[N],hh;
int nex[N],to1[N],to2[N],he[N],tot;
int e[N],st[N],top,k;
int To[N],num,Nex[N],last[N];
int dfn[N],zz;
int li[N],ri[N];
int ss[N];
int lowbit(int x){return (x&(-x));
}
void update(int x,int y){while (x<N){ss[x]+=y;x+=lowbit(x);}
}
int ask(int x){int s=0;while (x){s+=ss[x];x-=lowbit(x);}return s;}inline void add(int x,int y,int id){++tot;to1[tot]=y; to2[tot]=id; nex[tot]=head[x]; head[x]=tot;
}
inline void add1(int x,int y){to[++hh]=y; ne[hh]=he[x]; he[x]=hh;
}
void add2(int x,int y){To[++num]=y; Nex[num]=last[x]; last[x]=num;
}
inline void R(int &x){int t=0; char ch;for (ch=getchar();!('0'<=ch && ch<='9');ch=getchar());for (;('0'<=ch && ch<='9');ch=getchar()) t=t*10+ch-'0';x=t;
}
void work(){now=0;  dep=0;l=strlen(s+1); fo(i,1,l) {if ('a'<=s[i] && s[i]<='z') {fa=now;dep++;c=s[i]-'a';if (!ch[now][c]) ch[now][c]=++cnt; now=ch[now][c] ; Fa[now]=fa;}if (s[i]=='B') {dep--;now=Fa[now];}if (s[i]=='P') {++sum;add1(now,sum);wh[sum]=now;val[now]=1;}}
}
void build(){h=t=0; fo(i,0,25) if (ch[0][i]) q[++t]=ch[0][i];while (h<t) {r=q[++h];fo(i,0,25){u=ch[r][i];if (!u) continue; // 区别v=f[r];while (v && !ch[v][i]) v=f[v];f[u]=ch[v][i];q[++t]=u;}}
}void Dfs(int x){dfn[x]=++zz;li[x]=ri[x]=dfn[x];for (int i=last[x];i;i=Nex[i]){int v=To[i];Dfs(v);li[x]=min(li[x],li[v]);ri[x]=max(ri[x],ri[v]);}
}
void dg(int x){if (vis[x]) return;vis[x]=1;update(dfn[x],1);for (int i=head[x];i;i=nex[i]){d[to2[i]]=ask(ri[to1[i]])-ask(li[to1[i]]-1); }fo(i,0,25) {if (ch[x][i]) dg(ch[x][i]);}update(dfn[x],-1);
}
int main(){
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);scanf("%s",s+1);work();build();scanf("%d",&m);fo(i,1,m) {R(x); R(y);add(wh[y],wh[x],i);}fo(i,1,cnt) add2(f[i],i);Dfs(0);dg(0);fo(i,1,m)  printf("%d\n",d[i]);return 0;
}