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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define maxn 360010
using namespace std;
int n, m;
char s[maxn], c[maxn];
int l[maxn], r[maxn];
vector<int> a;
struct Edge {
int to, next;
} e[maxn]; int c1, head[maxn];
inline void add_edge(int u, int v) {
e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}
#define ch s[i] - 'a'
struct Trie {
int v, fail, nxt[26];
} T[maxn]; int rt = 1, top = 1;
void insert(char *s) {
int l = strlen(s), now = rt;
for (int i = 0; i < l; ++i) {
if (!T[now].nxt[ch]) T[now].nxt[ch] = ++top;
now = T[now].nxt[ch];
} a.push_back(now);
}
void init_fail() {
queue<int> Q;
for (int i = 0; i < 26; ++i) {
int &u = T[rt].nxt[i];
if (!u) { u = rt; continue; }
T[u].fail = rt; Q.push(u);
add_edge(rt, u);
}
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (int i = 0; i < 26; ++i) {
int &v = T[u].nxt[i];
if (!v) { v = T[T[u].fail].nxt[i]; continue; }
T[v].fail = T[T[u].fail].nxt[i]; Q.push(v);
add_edge(T[v].fail, v);
}
}
}
#undef ch
int in[maxn], out[maxn], c2;
void dfs(int u, int fa) {
in[u] = ++c2;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
dfs(v, u);
} out[u] = c2;
}
struct Zhuxi {
#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct zhuxi {
int v, ch[2];
} T[maxn * 20]; int top, rt[maxn];
void update(int &i, int j, int l, int r, int k, int v) {
i = ++top; T[i] = T[j]; T[i].v += v;
if (l == r) return ; int m = l + r >> 1;
if (k <= m) update(lc, Lc, l, m, k, v);
else update(rc, Rc, m + 1, r, k, v);
}
int query(int i, int j, int l, int r, int L, int R) {
if (l > R || r < L) return 0;
if (L <= l && r <= R) return T[j].v - T[i].v;
int m = l + r >> 1;
return query(lc, Lc, l, m, L, R) + query(rc, Rc, m + 1, r, L, R);
}
} _;
vector<int> A[maxn];
int pre[maxn];
int main() { fill(head, head + maxn, -1);
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
l[i] = r[i - 1] + 1;
cin >> s + l[i];
r[i] = l[i] + strlen(s + l[i]) - 1;
}
for (int i = 1; i <= m; ++i) cin >> c, insert(c);
init_fail(); dfs(rt, 0);
for (int o = 1; o <= n; ++o) {
int now = rt;
for (int i = l[o]; i <= r[o]; ++i) {
now = T[now].nxt[s[i] - 'a'];
A[in[now]].push_back(o);
}
}
for (int i = 1; i <= top; ++i) {
_.rt[i] = _.rt[i - 1];
for (auto u : A[i]) {
_.update(_.rt[i], _.rt[i], 0, top, pre[u], 1);
pre[u] = i;
}
}
for (auto u : a)
cout << _.query(_.rt[in[u] - 1], _.rt[out[u]], 0, top, 0, in[u] - 1) << "\n";
return 0;
}
|