开发笔记:AC自动机解决字符集很大的情况(可持久化数组优化getfail的过程)

今天遇到了一个问题&＃xff0c;那就是如果 $AC$ 自动机的字符集很大该怎么办&＃xff1f;比如改成 $1e5$ 该怎么办呢&＃xff1f;

例如下题&＃xff1a;

题目来源转自&＃xff08;侵权删&＃xff09;&＃xff1a;点击查看

先不考虑解法&＃xff0c;肯定是需要用 $AC$ 自动机去解决的&＃xff0c;但是问题是&＃xff0c;本题中字符串的总长度可能达到




O


(



n


2



)



O(n^2)


O(n2) 级别&＃xff0c;加上字符集特别大&＃xff0c;所以遇到了很多问题

不过不难看出题目中给出的实际上就是一棵 $trie$ 树&＃xff0c;我们可以直接在 $trie$ 树上 $getfail$&＃xff0c;就可以构建出 $AC$ 自动机了&＃xff0c;现在的问题转换为&＃xff0c;如何处理字符集很大的情况

先看普通的 $getfail$ 的模板&＃xff1a;

void getfail()
{
queue<int>q;
for(int i&＃61;0;i<26;i&＃43;&＃43;)
{
if(trie[0][i])
{
fail[trie[0][i]]&＃61;0;
q.push(trie[0][i]);
}
}
while(!q.empty())
{
int cur&＃61;q.front();
q.pop();
for(int i&＃61;0;i<26;i&＃43;&＃43;)
{
if(trie[cur][i])
{
fail[trie[cur][i]]&＃61;trie[fail[cur]][i];
q.push(trie[cur][i]);
}
else
trie[cur][i]&＃61;trie[fail[cur]][i];
}
}
}


简单的思路肯定是直接把 $26$ 改成 $1e5$&＃xff0c;很可惜这样显然是会 $TLE$ 的

考虑 $bfs$ 转移的瓶颈出现在哪里呢&＃xff1f;通过分析后不难看出实际上就是上面代码第 $24$ 行的

trie[cur][i]&＃61;trie[fail[cur]][i];


的这句代码&＃xff0c;转移了太多无用的状态。对于每一层的转移&＃xff0c;实际上只有很少的情况进入到了 $if$ 语句里

所以假设&＃xff0c;我们开一个 $unordered\_map<int,int>trans[N]$ 用于储存题目中给出的字典树&＃xff0c;其中 $trans[u][to]\&＃61;v$ 表示在字典树中从点 $u$ 经过一条权值为 $to$ 的边可以到达点 $v$。再开一个 $unordered\_map<int,int>trie[N]$ 用于储存 $getfail$ 的转移过程&＃xff0c;则将上述代码改进一下&＃xff1a;

void getfail()
{
queue<int>q;
for(auto it:trans[0])
{
int u&＃61;0,v&＃61;it.second,to&＃61;it.first;
trie[u][to]&＃61;v;
fail[v]&＃61;u;
q.push(v);
}
while(!q.empty())
{
int u&＃61;q.front();
q.pop();
trie[u]&＃61;trie[fail[u]];
for(auto it:trans[u])
{
int v&＃61;it.second,to&＃61;it.first;
trie[u][to]&＃61;v;
fail[trie[u][to]]&＃61;trie[fail[u]][to];
q.push(trie[cur][to]);
}
}
}


如此一来&＃xff0c;干脆把 $if-else$ 分支直接删除掉了。不过又出现了新的问题&＃xff0c;如何快速执行第 $15$ 行的赋值操作呢&＃xff1f;

这里就要引入可持久化数组了&＃xff0c;所谓可持久化数组&＃xff0c;就是可以访问历史版本的&＃xff0c;支持单点更新和单点查询的主席树

如此一来就完美解决了这个模型

代码&＃xff1a;

const int N&＃61;1e6&＃43;100;
const int M&＃61;1e5;
unordered_map<int,int>trans[N];
struct Node {
int l,r,val;
}tree[N];
int trie[N],fail[N],tot;
int newnode() {
tot&＃43;&＃43;;
tree[tot].l&＃61;tree[tot].r&＃61;tree[tot].val&＃61;0;
return tot;
}
void add(int &k,int pos,int val,int l,int r) {
int nk&＃61;newnode();
tree[nk]&＃61;tree[k];
k&＃61;nk;
if(l&＃61;&＃61;r) {
tree[k].val&＃43;&＃61;val;
return;
}
int mid&＃61;(l&＃43;r)>>1;
if(pos<&＃61;mid) {
add(tree[k].l,pos,val,l,mid);
} else {
add(tree[k].r,pos,val,mid&＃43;1,r);
}
}
int ask(int k,int pos,int l,int r) {
if(l&＃61;&＃61;r) {
return tree[k].val;
}
int mid&＃61;(l&＃43;r)>>1;
if(pos<&＃61;mid) {
return ask(tree[k].l,pos,l,mid);
} else {
return ask(tree[k].r,pos,mid&＃43;1,r);
}
}
void getfail() {
queue<int>q;
for(auto it:trans[0]) {
int u&＃61;0,v&＃61;it.second,to&＃61;it.first;
add(trie[u],to,v,1,M);
fail[v]&＃61;u;
q.push(v);
}
while(q.size()) {
int u&＃61;q.front();
q.pop();
trie[u]&＃61;trie[fail[u]];
for(auto it:trans[u]) {
int v&＃61;it.second,to&＃61;it.first;
int delta&＃61;v-ask(trie[u],to,1,M);
add(trie[u],to,delta,1,M);
fail[v]&＃61;ask(trie[fail[u]],to,1,M);
q.push(v);
}
}
}
void init() {
tot&＃61;-1;
newnode();
}