题目描述
输入
输出
样例输入
4 3 xyz xyz zzx xzz
样例输出
2 1 2 1
提示
Solution
trie树
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<cstdio> #include<iostream> using namespace std; int n,m,tot,f[1000010][3]; long long a[1000010],ans[100010]; char s[100010]; void change() { int now=1; for (int i=1;i<=m;i++) { int t=s[i]-'x'; if (f[now][t]!=0) now=f[now][t]; else f[now][t]=++tot,now=tot; } a[now]++; } void query(int id,int t,int y) { if (y>m) { ans[t]+=a[id]; return; } for (int i=0;i<=2;i++) { char ch=i+'x'; if (f[id][i]!=0) query(f[id][i],t+(ch==s[y]),y+1); } } int main() { scanf("%d%d",&n,&m); tot=1; for (int i=1;i<=n;i++) { scanf("%s",s+1); query(1,0,1); change(); } for (int i=0;i<=m;i++) printf("%lld\n",ans[i]); return 0; } /*********** |
