看到题面就是多模式串匹配，显然考虑 $AC$ 自动机
但是一个个匹配显然太慢了，想想匹配时在做什么，对于一个文本串，我们在自动机上走走走，每到一个位置就把那个位置的标记 $+1$，最后一波 $dfs$ 统计 $fail$ 树子树的标记和，然后对于某个模式串，它在自动机上结束节点的子树和就是它在文本串中出现的次数
对于这一题，文本串同时也是模式串，我们可以在插入模式串的时候，顺便把标记先打上，最后只要一遍 $dfs$ 统计即可
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e6+7; int n; char s[N]; namespace ACM { int ch[N][27],fail[N],sz[N],match[N],cnt; int fir[N],from[N],to[N],cntt; inline void add(int u,int v) { from[++cntt]=fir[u]; fir[u]=cntt; to[cntt]=v; } void ins(int p) { int u=0,len=strlen(s+1); for(int i=1;i<=len;i++) { int v=s[i]-'a'; if(!ch[u][v]) ch[u][v]=++cnt; u=ch[u][v]; sz[u]++; } match[p]=u; } queue <int> Q; void build() { for(int i=0;i<26;i++) if(ch[0][i]) Q.push(ch[0][i]); while(!Q.empty()) { int u=Q.front(); Q.pop(); for(int i=0;i<26;i++) { int &v=ch[u][i]; if(!v) v=ch[fail[u]][i]; else fail[v]=ch[fail[u]][i],Q.push(v); } } for(int i=1;i<=cnt;i++) add(fail[i],i); } void dfs(int u) { for(int i=fir[u];i;i=from[i]) dfs(to[i]),sz[u]+=sz[to[i]]; } void solve() { dfs(0); for(int i=1;i<=n;i++) printf("%d ",sz[match[i]]); } } int main() { n=read(); for(int i=1;i<=n;i++) { scanf("%s",s+1); ACM::ins(i); } ACM::build(); ACM::solve(); return 0; }