今天遇到了一個問題，那就是如果 $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的过程)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。