AC自动机和Fail树

大家好，又见面了，我是你们的朋友全栈君。

AC自动机和Fail树

萌新第一次试着写博客…全是口胡(/□＼*)，可能以后也不会有时间再写了

相关数据结构：AC自动机，树状数组（线段树）

Fail指针的基本性质：某只结点的Fail指针，指向它所代表的字符串的最长的后缀的结点。

性质：每只结点沿着其Fail指针一直走，最终会走到根节点。

这样，将每只结点和其Fail指针指向的结点连边，就形成了一个树，其根与原Trie树相同，称为Fail树。

性质：

1 某个结点$A$，它子树中的所有节点在Trie图中沿Fail指针一直走，会走到$A$结点，这说明这些结点所代表的前缀都是$A$的后缀。

2 该结点沿Fail指针向根走，经过的所有结点所代表的串都是该结点$A$的后缀。

例子：

对每一个模式串$s_i$，将它所有前缀所代表的结点的权值$+1$，再求以$A$为根的子树的权值和，就是$A$在所有模式串中出现的次数。

具体地，我们可以递归地求权和，也可以用DFS序，求该结点区间的区间和。（单点更新、区间查询）

还记得吗？AC自动机可以求所有模式串在待匹配串中出现的总次数。

例：[NOI2011]阿狸的打字机

题目描述

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

·输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

·按一下印有’B’的按键，打字机凹槽中最后一个字母会消失。

·按一下印有’P’的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。

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

a aa ab

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

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

输入输出格式

输入格式：

输入的第一行包含一个字符串，按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数m，表示询问个数。

接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y，表示第i个询问为$(x,y)$。

输出格式：

输出m行，其中第i行包含一个整数，表示第i个询问的答案。

思考：

本题要求任意一个串在给定的串中的出现次数，可能有100000次询问，AC自动机和KMP等等显然都不行。

根据Fail树的性质，一只以结点$A$为根的子树中的结点，一定含有$A$串做后缀。那么如果$A$是某个串的结束结点，那么$A$串就在这些结点的串中出现过。那么对于另一个串$B$，它的结点有多少在$A$子树中出现，那么$A$就在$B$中出现了多少次。这就变成了一个子树求和问题。

求子树的权值和可以用上述提到的DFS序结合树状数组来做。但是怎样只求一个特定的串的权值和呢？在遍历Trie树的时候，给当前搜索路径上所有结点的权值$+1$，退出时再$-1$，这样就保证只有搜索路径上的结点有权值$1$。每当DFS到一只结束结点时，它所对应的串$B$的所有节点都在搜索路径上。这样要求$A$在$B$中的出现次数，只要求$A$子树的权值和就好啦。

预先将查询按照$y$排序，每DFS到一只结束结点$y$，就处理该结束结点的所有查询：对每个$(x,y)$都进行区间求和的操作，复杂度$O(logn)$。一共是$O((n+m)logn)$。

(祖传的郭老师数算实习课上的AC自动机模板…码风枣糕ヽ(･ω･´ﾒ)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define N 100005
#define inf 0x7fffff
#define lb(x) ((x)&-(x))
char s[N];
int nodeCnt = 2, pCnt, q, l;
int dfn[N], Time, Range[N][2], ans[N];
struct Quest{ 

int x, y, index;
bool operator<(const Quest &op) const { 
 return y < op.y; }
Quest(){ 
}
Quest(int _y):y(_y){ 
}
}Q[N];
struct Node{ 

Node *child[26], *prev, *fa;
vector<Node *> fail;
int poi; //代表打印次序编号
}T[N];
/* 一只树状数组 */
struct TreeA{ 

int C[N];
void Upd(int x, int v = 1){ 
 while(x<=nodeCnt){ 

C[x]+=v, x+=lb(x);
}
}
int Sum(int x){ 

int sum = 0;
while(x){ 

sum += C[x];
x -= lb(x);
}
return sum;
}
TreeA() { 
 memset(C, 0, sizeof(C)); }
}TA;
void BuildTrie(){ 

Node *now = T + 1;
for (int i = 0; s[i]; i++){ 

if(s[i]=='P'){ 

now->poi = ++pCnt;
continue;
}
if(s[i]=='B'){ 

now = now->fa;
continue;
}
if(!now->child[s[i]-'a']){ 

now->child[s[i] - 'a'] = T + nodeCnt++;
now->child[s[i] - 'a']->fa = now;
}
now = now->child[s[i] - 'a'];
}
}
/* 建立一只fail树 */
void BuildFail(){ 

for (int i = 0; i < 26;i++)
T->child[i] = T + 1;
(T + 1)->prev = T;
queue<Node *> q;
q.push(T + 1);
while(!q.empty()){ 

Node *now = q.front();
q.pop();
for (int i = 0; i < 26;i++)
if(now->child[i]){ 

Node *prev = now->prev;
while(!prev->child[i])
prev = prev -> prev;
now->child[i]->prev = prev->child[i];
prev->child[i]->fail.push_back(now->child[i]);
q.push(now->child[i]);
}
}
}
/* 遍历Fail树，找到它的DFS序 */
void DFN(Node* r){ 

dfn[r - T] = ++Time;
for (int i = 0; i < r->fail.size(); i++)
DFN(r->fail[i]);
if(r->poi)
Range[r->poi][1] = Time,Range[r->poi][0]=dfn[r-T];
}
/* 遍历Trie树，不断处理查询 */
void DFS(Node* r){ 

TA.Upd(dfn[r - T]);   /* 搜索路径上结点权值+1 */
if(r->poi){ 

int now = lower_bound(Q, Q + q, Quest(r->poi)) - Q;
for (; Q[now].y == r->poi;now++){ 

int x = Q[now].x;
ans[Q[now].index] = TA.Sum(Range[x][1]) - TA.Sum(Range[x][0] - 1);
}
}
for (int i = 0; i < 26;i++)
if(r->child[i])
DFS(r->child[i]);
TA.Upd(dfn[r - T], -1); /* 不在搜索路径上了 权值为0 */
}
int main(){ 

scanf("%s", s);
BuildTrie();
BuildFail();
DFN(T+1);
cin >> q;
for (int i = 0; i < q;i++){ 

scanf("%d%d", &Q[i].x, &Q[i].y);
Q[i].index = i;
}
sort(Q, Q + q);
DFS(T+1);
for (int i = 0; i < q;i++)
printf("%d\n", ans[i]);
return 0;
}