1 #include <bits/stdc++.h>
2
3 using namespace std;
4
5 const int N = 510*505;
6 const int M = 27;
7
8
9 map<string,int>Map;
10 struct Trie
11 {
12 int next[N][M],fail[N],end[N];
13 int root,L;
14 int newnode()
15 {
16 for(int i = 0; i < 26; i++)
17 next[L][i] = -1;
18 end[L++] = -1;
19 return L - 1;
20 }
21 void init()
22 {
23 L = 0;
24 root = newnode();
25 }
26 void insert(string s,int id)
27 {
28 int len = s.size();
29 int now = root;
30 for(int i = 0; i < len; i++)
31 {
32 if(next[now][s[i]-'a'] == -1)
33 next[now][s[i] - 'a'] = newnode();
34 now = next[now][s[i] - 'a'];
35 }
36 end[now] = id;
37 }
38 void build()
39 {
40 queue<int>Q;
41 fail[root] = root;
42 for(int i = 0; i < 26; i++)
43 {
44 if(next[root][i] == -1)
45 next[root][i] = root;
46 else
47 {
48 fail[next[root][i]] = root;
49 Q.push(next[root][i]);
50 }
51 }
52 while(!Q.empty())
53 {
54 int now = Q.front();
55 Q.pop();
56 for(int i = 0; i < 26; i++)
57 {
58 if(next[now][i] == -1)
59 next[now][i] = next[fail[now]][i];
60 else
61 {
62 fail[next[now][i]] = next[fail[now]][i];
63 Q.push(next[now][i]);
64 }
65 }
66 }
67 }
68 int num[1000];
69 void query(char buf[],int n,int mm[])
70 {
71 for(int i = 1; i <= n; i++)
72 num[i] = 0;
73 int len = (int)strlen(buf);
74 int now = root;
75 for(int i = 0; i < len; i++)
76 {
77 now = next[now][buf[i]-'a'];
78 int temp = now;
79 while( temp != root )
80 {
81 if( end[temp] != -1)
82 num[end[temp]]++;
83 temp = fail[temp];
84 }
85 }
86 for(int i = 1; i <= n; i++)
87 printf("%d
",num[mm[i]]);
88 }
89 };
90
91 char buf[1000100];
92 Trie ac;
93
94 void solve()
95 {
96 ac.init();
97 int n, l = 0;
98 scanf("%d",&n);
99 scanf("%s",buf);
100 Map.clear();
101 int twice[1005];
102 memset(twice,0,sizeof(twice));
103 for(int i = 1; i <= n; i++)
104 {
105 string ss;
106 cin>>ss;
107 int c = Map[ss];
108 if(c == 0)
109 {
110 Map[ss] = ++l;
111 ac.insert(ss,l);
112 }
113 twice[i] = Map[ss];
114 //int tmp = Map[ss];
115
116 }
117 ac.build();
118
119 ac.query(buf,n,twice);
120 }
121
122 int main(void)
123 {
124 int t,cnt = 0;
125 scanf("%d",&t);
126 while(t--)
127 {
128 printf("Case %d:
",++cnt);
129 solve();
130 }
131
132 return 0;
133 }
