Trie树的模板题。我们把每个人都存在Trie树里面，然后再每个人跑一遍即可。注意一个人走过之后要清零，否则的话会被重复计算。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<queue> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 40005; const int N = 500005; const ll mod = 1000000007; int read() { int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } int n,m,ans[M]; char s[M][50]; struct trie { int c[N][26],cnt,val[N]; bool vis[N]; void clear() { memset(c,0,sizeof(c)); memset(val,0,sizeof(val)); memset(vis,0,sizeof(vis)); cnt = 0; } void insert(char *p) { int l = strlen(p),u = 0; rep(i,0,l-1) { int v = p[i] - 'A'; if(!c[u][v]) c[u][v] = ++cnt; u = c[u][v]; if(i == l-1) val[u]++; } } void find(char *p) { int l = strlen(p),u = 0; rep(i,0,l-1) { int v = p[i] - 'A'; u = c[u][v]; if(i == l-1 && val[u]) ans[val[u]]++,val[u] = 0; } } }T; int main() { while(1) { n = read(),m = read(); if(!n && !m) break; T.clear(); memset(ans,0,sizeof(ans)); rep(i,1,n) scanf("%s",s[i]),T.insert(s[i]); rep(i,1,n) T.find(s[i]); rep(i,1,n) printf("%d ",ans[i]); } return 0; }