[NOI2011]阿狸的打字机

摘要

好一个AC自动机+树状数组的题

打字机上只有28个按键,分别印有26个小写英文字母和’B’、’P’两个字母。经阿狸研究发现,这个打字机是这样工作的:

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

例如,阿狸输入aPaPBbP,纸上被打印的字符如下:a aa ab.

我们把纸上打印出来的字符串从1开始顺序编号,一直到n。每次询问两个数(x,y)(其中 ),输出第x个打印的字符串在第y个打印的字符串中出现了多少次。 .

一道小清新的题,需要我们对AC自动机的性质有深入的了解

fail树与子串的关系

AC自动机的结点表示某个模式串的前缀,我们称为状态;fail指针呈树形结构,我们将这颗树称作fail树.根据fail指针的定义我们知道,fail树上每个结点的祖先结点代表的状态都是这个结点的状态的后缀。而一个状态的子串就是这个状态的某个前缀的后缀。

因此对于一组询问 ,我们找到代表y状态的结点 ,我们知道,在Trie上u到根节点路径上的结点就是y的所有前缀,因此如果x出现在y中,那么状态x一定能由y的某个前缀跳fail指针跳到,即x在y中出现的次数等于fail树上以x为根的子树中,y的所有前缀出现的次数。

p1

如图,由 组成的Trie中,红色/黄色的为fail指针,对于状态 中出现的次数就是y的前缀在 的fail子树中出现的结点数,即橙色结点。

树上问题转化为序列问题

把询问按照 分类,每次直接在树上维护信息,复杂度较高。由于我们求的是子树内的结点数,而树的DFS序列中子树对应着区间,因此我们可以直接对fail树求DFS序列,转化为求区间内的点的个数。因此对于y的询问,我们把y的前缀状态对应的区间贡献到DFS序列的对应位置,然后查询区间和即可。

不过这样做的实质与树上维护没有区别,复杂度仍然没有减少。导致复杂度过高的原因是不同的y是有重复的结点的,而这些结点被多次在序列上添加删除,导致复杂度过高。能否使得每个结点只被添加/删除一次?合理安排y的顺序,我们按照y在Trie上的DFS序来依次处理询问即可。相当于每次我们维护的y就是Trie的y状态结点到根节点的路径,因此按照DFS序处理,回溯的时候删除,就只需要删除1次。

我们的序列操作则变成:

  • 单点加 .
  • 区间求和

树状数组维护即可,总复杂度 .

#include<bits/stdc++.h>
using namespace std;
const int L=2e5+5;
char s[L];
struct data{int x,idx;};//x编号;idx询问的编号
vector<data> qry[L];
int m;

int tr[L][26],tot;
int fail[L],idx[L],idxcnt;//如果这个点对应一个模式串,idx表示其对应的标号
int nod[L];//nod[i]表示编号为i的模式串对应的trie结点标号

void maketrie(){//从s中插入,当前结点为u,状态为s[i]
int u=0,st[L],tp=0;//手写递归栈
for(int i=1;s[i];i++){
if(s[i]=='P')idx[u]=++idxcnt,nod[idxcnt]=u;
else if(s[i]=='B')u=st[tp],tp--;
else {
st[++tp]=u;//记录回溯结点
if(!tr[u][s[i]-'a'])tr[u][s[i]-'a']=++tot;
u=tr[u][s[i]-'a'];
}
}
}
int tseq[L*2],tseqcnt;//trie上dfs序列
void trieDfs(int u){
tseq[++tseqcnt]=u;;
for(int i=0;i<26;i++)if(tr[u][i])trieDfs(tr[u][i]);
tseq[++tseqcnt]=u;
}
queue<int> q;
void build(){//建立AC自动机
for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);
while(q.size()){
int u=q.front();q.pop();
for(int i=0;i<26;i++){
if(tr[u][i])fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
else tr[u][i]=tr[fail[u]][i];
}
}
}
//fail树
struct qxx{int nex,t;};
qxx e[L];
int h[L],cnt;
void add_path(int f,int t){e[++cnt]=(qxx){h[f],t},h[f]=cnt;}

int fseq[L][2],fseqcnt;//fail树的DFS序列

void failTreeDfs(int u){
fseq[u][0]=++fseqcnt;
for(int i=h[u];i;i=e[i].nex)failTreeDfs(e[i].t);
fseq[u][1]=++fseqcnt;
}
void buildFailTree(){
for(int i=1;i<=tot;i++)add_path(fail[i],i);
failTreeDfs(0);
}
//树状数组
namespace BIT{
int c[L];
void add(int p,int v){for(int i=p;i<=fseqcnt;i+=i&-i)c[i]+=v;}
int pre(int p,int res=0){for(int i=p;i>0;i-=i&-i)res+=c[i];return res;}
}
int ans[L];
bool vis[L];//标记是否处于搜索or回溯阶段
void calc(){//在trie上dfs,顺便处理询问
for(int i=1;i<=tseqcnt;i++){
const int &u=tseq[i];//当前结点编号
if(!vis[u]){
vis[u]=1,BIT::add(fseq[u][0],1);//添加结点u的信息
if(!idx[u])continue;
//处理和y=idx[u]有关的询问
const int &y=idx[u];
for(int i=0;i<qry[y].size();i++){
const int &x=qry[y][i].x,&id=qry[y][i].idx;
ans[id]+=BIT::pre(fseq[nod[x]][1])-BIT::pre(fseq[nod[x]][0]-1);
}
}
else BIT::add(fseq[u][0],-1);//删除结点信息
}
}
int main(){
scanf("%s",s+1);
maketrie();
trieDfs(0);
build();
buildFailTree();
scanf("%d",&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
qry[y].push_back((data){x,i});
}
calc();
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}
/*
* 字典图只是在字典树的基础上加边,因此字典图里包含原字典树的结构
* 每个结点代表某个模式串的前缀
* fail树的性质:每个结点的祖先结点代表这个结点的后缀
* 子串即前缀的后缀
* 对于(x,y)的询问,把y的所有前缀结点打个标记
* 我们相当于求x对应的结点的fail子树中标记的个数
* 因此对于y相同的询问放在一起做
* 那么y怎么排序?按照y的dfs序排列,这样每个结点只会被添加删除一次
* 用DFS序转化为序列问题,每个结点对应序列上区间端点
* 相当于单点修改,区间求和,树状数组维护即可;
* BUG#1: 没有调用nod[x]指针
* BUG#2: 内存没开够
*/