阿貍的打字機

題解

題目中給出的字符串就是構建$Trie$樹的順序.我們將字符串依次讀入,每讀入一個小寫字符就相當于在$Trie$樹當前節點下插入一個小寫字符,讀入$B$時,就在$Trie$樹中向父節點移動一步.讀入$P$的時候,就做一個標記.

然后對這顆$Trie$樹構建$AC$自動機.

找找規律發現第$x$串在第$y$串中出現的次數就是$Trie$樹上$x$串尾點到$y$串末尾點的樹鏈上,所有能直接或間接通過$fail$指針跳到$x$串末尾點的點的個數.

觀察到自動機上$fail$指針構成了一顆$fail$樹.

進一步我們發現,所有能直接或間接跳到$x$串末尾點的點就是$fail$樹上,$x$節點的子樹大小.

而實際的答案就是$fail$樹上$x$串末尾點的子樹與$Trie$樹上$x$到$y$的樹鏈的交集中點的個數.

我們對$fail$樹做一遍$dfs$序,用這個$dfs$序就可以查詢和維護$fail$樹的子樹的信息了.

對這個$dfs$序列建立一個樹狀數組.

然后我們對$Trie$樹做一遍$dfs$,在$dfs$的過程中,把當前點在樹狀數組中的$dfn$位置$+1$,返回的時候在該位置$?1$,這樣相當于在$Trie$樹中從當前點到根節點的樹鏈上所有節點都已經在樹狀數組中激活了,對于當前點作為$y$的詢問,在$fail$樹的以$x$為根的子樹中計算有多少個點被激活就ok了(樹狀數組查詢前綴和).

代碼

#include <iostream> #include <algorithm> #include <cstring> #include <queue> #include <vector> #define pr(x) std::cout << #x << ':' << x << std::endl #define rep(i,a,b) for(int i = a;i <= b;++i) #define LETTER 26 typedef std::pair<int,int> pii; const int N = 100010; char s[N]; struct Trie{int num,fail,fa;int next[LETTER]; }pool[N]; Trie* const trie = pool + 1; int cnt; void init() {cnt = 0;memset(pool,0,2*sizeof(Trie));trie[0].fail = -1; } int now; int pat[N]; int pc; std::vector<int> trie_edge[N]; void build() {pc = now = 0;for(int i = 0;s[i];++i) {if(s[i] == 'B') now = trie[now].fa;else if(s[i] == 'P') pat[++pc] = now;else {int &pos = trie[now].next[s[i]-'a'];if(!pos) {pos = ++cnt;memset(&trie[pos],0,sizeof(Trie));trie[pos].fa = now;trie_edge[now].push_back(pos);}now = pos;}}std::queue<int> Q;Q.push(0);while(!Q.empty()) {int t = Q.front();Q.pop();for(int i = 0;i < LETTER;++i) {int &cur = trie[t].next[i];if(cur) {Q.push(cur);trie[cur].fail = trie[trie[t].fail].next[i];}else cur = trie[trie[t].fail].next[i];}} } int bitree[N<<1]; int lowbit(int x) {return x & (-x);} int sum(int pos) {int res = 0;for(;pos;pos -= lowbit(pos)) res += bitree[pos];return res; } void add(int pos,int x) {for(;pos < N<<1;pos += lowbit(pos))bitree[pos] += x; }std::vector<int> edge[N]; int beg[N],end[N]; int idx = 0; void dfs1(int u){beg[u] = ++idx;for(int v : edge[u]) dfs1(v);end[u] = ++idx; } std::vector<pii> query[N]; int ans[N]; void dfs2(int u) {add(beg[u],1);for(pii p : query[u]) {int x = p.first,id = p.second;ans[id] = sum(end[x])-sum(beg[x]-1);}for(int v : trie_edge[u])dfs2(v);add(beg[u],-1); }int main() {init();std::ios::sync_with_stdio(false);std::cin >> s;build();for(int i = 1;i <= cnt;++i) edge[trie[i].fail].push_back(i);dfs1(0);int m;std::cin >> m;for(int i = 1;i <= m;++i) {int x,y;std::cin >> x >> y;query[pat[y]].push_back((pii){pat[x],i});}dfs2(0);for(int i = 1;i <= m;++i) {std::cout << ans[i] << std::endl;}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的P2414 NOI2011阿狸的打字机 [AC自动机,dfs序]的全部內容，希望文章能夠幫你解決所遇到的問題。

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