正題

題目鏈接:https://www.luogu.com.cn/problem/P6257

---

題目大意

給出一個字典樹，$k$次詢問求每個節點出發到根節點的路徑有多少包含前綴$s_i$。

---

解題思路

我們按照所有詢問串的反串構造$AC$自動機。

那么此時如果我們用一個串$S$上去跑匹配的話，那么跑到的節點就表示該串在所有$AC$自動機上的串擁有的最長后綴。然后其他存在的后綴一定在這個點到根的$fail$鏈上。

然后我們丟一個$Trie$樹上去匹配，跑到的點$cnt++$，之后在$fail$樹上統計子樹的$cnt$和即可。

時間復雜度$O(n\sum |s|)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=1e6+1; int n,k,tot,ch[N][26],t[N][26],cnt[N],in[N],pos[N],fail[N]; char s[N]; queue<int> q; int Insert(char *s){int l=strlen(s+1),x=0;for(int i=l;i>=1;i--){int c=s[i]-'A';if(!t[x][c])t[x][c]=++tot;x=t[x][c];}return x; } void Get_Fail(){for(int i=0;i<26;i++)if(t[0][i])q.push(t[0][i]);while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<26;i++){if(!t[x][i])t[x][i]=t[fail[x]][i];else{fail[t[x][i]]=t[fail[x]][i];q.push(t[x][i]);}}}return; } void Dfs(int x,int y){cnt[y]++;for(int i=0;i<26;i++)if(ch[x][i])Dfs(ch[x][i],t[y][i]);return; } void Calc(){for(int i=1;i<=tot;i++)in[fail[i]]++;for(int i=0;i<=tot;i++)if(!in[i])q.push(i);while(!q.empty()){int x=q.front();q.pop();cnt[fail[x]]+=cnt[x];in[fail[x]]--;if(!in[fail[x]])q.push(fail[x]);}return; } int main() {scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){int x;char op[3];scanf("%s%d",op,&x);ch[x][op[0]-'A']=i;}for(int i=1;i<=k;i++){scanf("%s",s+1);pos[i]=Insert(s);}Get_Fail();Dfs(0,0);Calc();for(int i=1;i<=k;i++)printf("%d\n",cnt[pos[i]]); }

總結

以上是生活随笔為你收集整理的P6257-[ICPC2019 WF]First of Her Name【AC自动机】的全部內容，希望文章能夠幫你解決所遇到的問題。

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