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

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

例如下题：

题目来源转自（侵权删）：点击查看

先不考虑解法，肯定是需要用 $AC$ 自动机去解决的，但是问题是，本题中字符串的总长度可能达到 $O(n^2)$ 级别，加上字符集特别大，所以遇到了很多问题

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

先看普通的 $getfail$ 的模板：

void getfail() {queue<int>q;for(int i=0;i<26;i++){if(trie[0][i]){fail[trie[0][i]]=0;q.push(trie[0][i]);}}while(!q.empty()){int cur=q.front();q.pop();for(int i=0;i<26;i++){if(trie[cur][i]){fail[trie[cur][i]]=trie[fail[cur]][i];q.push(trie[cur][i]);}elsetrie[cur][i]=trie[fail[cur]][i];}} }

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

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

trie[cur][i]=trie[fail[cur]][i];

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

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

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

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

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

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

代码：

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

总结

以上是生活随笔为你收集整理的AC自动机解决字符集很大的情况(可持久化数组优化getfail的过程)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。