[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: 内存没开够
 */

 上一篇
NOI2016 优秀的拆分 NOI2016 优秀的拆分
摘要 人生第二道黑题~ 如果一个字符串可以被拆分为 AABB 的形式,其中 A 和 B 是任意非空字符串,则我们称该字符串的这种拆分是优秀的。例如,对于字符串 aabaabaa,如果令 A=aab,B=a,我们就找到了这个字符串拆分成
2019.04.10
下一篇 
[NOI2014] 动物园 [NOI2014] 动物园
摘要 题意:对字符串的每个前缀求长度小于等于一半的 的个数 许多题解里都说可以在求 的时候顺便求,笔者没有想到这个思路。根据 的树形结构,其实相当于在树上找到根结点路径上编号小于等于一半的
2019.04.10
  目录