模板:洛谷P5357
code:
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int fail[N],tr[N][26],idx,n,times[N];
//end[i]表示第i个字符的结尾编号
int ed[N];
vector<int> edges[N];
void insert(int i,string &s){int cur=0;for(char &ch:s){int path=ch-'a';if(!tr[cur][path])tr[cur][path]=++idx;cur=tr[cur][path];}ed[i]=cur;
}void dfs(int u){for(int &v:edges[u]){dfs(v);times[u]+=times[v];}
}void init(){queue<int> q;for(int i=0;i<26;i++){if(tr[0][i]){q.push(tr[0][i]);}}while(q.size()){int u=q.front();q.pop();for(int i=0;i<26;i++){//存在更新fail,不存在更新直通表if(tr[u][i]){fail[tr[u][i]]=tr[fail[u]][i];q.push(tr[u][i]);}else{tr[u][i]=tr[fail[u]][i];}}}
}
int main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){string t;cin>>t;insert(i,t);}string s;cin>>s;//初始化直通表和fail数组init();int m=s.size();for(int cur=0,i=0;i<m;i++){cur=tr[cur][s[i]-'a'];//增加匹配次数times[cur]++;}//建反图for(int i=1;i<=idx;i++){edges[fail[i]].push_back(i);}//遍历fail指针建的树//汇总每个节点的词频dfs(0);for(int i=1;i<=n;i++){cout<<times[ed[i]]<<endl;}return 0;
}