记得平衡复杂度
又及: 这是一个悲惨的故事: 我又忘push了
懵逼的 题目
BZOJ
扯淡的 题解
这题暴跳fail也才\(\mathrm O(2
\times 10^8)\)不是...
那写啥正解啊
预处理fail的时候要把终点标记沿着fail下放,
不然复杂度就是\(\mathrm
O(10^{10})\)左右了
沙茶的 代码
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
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define MAXN (1000200 + 5)
#define MAXC (27)
using namespace std;
struct node {
int son[MAXC], fail;
vector<int> bh;
} b[MAXN];
int ans[MAXN], cntb, n, ns;
char s[MAXN], sn[MAXN];
void init() {
queue<int> q;
for (int i = 0; i < MAXC; i++) if (b[0].son[i]) q.push(b[0].son[i]);
while (!q.empty()) {
int dq = q.front();
q.pop();
for (int i = 0; i < b[b[dq].fail].bh.size(); i++)
b[dq].bh.push_back(b[b[dq].fail].bh[i]);
for (int i = 0; i < MAXC; i++)
if (b[dq].son[i]) b[b[dq].son[i]].fail = b[b[dq].fail].son[i], q.push(b[dq].son[i]);
else b[dq].son[i] = b[b[dq].fail].son[i];
}
}
void pd(int dq) {
for (int j = 0; j < b[dq].bh.size(); j++)
++ans[b[dq].bh[j]];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s);
int dqn = strlen(s), dq = 0;
for (int j = 0; j < dqn; j++) {
if (!b[dq].son[s[j] - 'a']) b[dq].son[s[j] - 'a'] = ++cntb;
dq = b[dq].son[s[j] - 'a'];
sn[++ns] = s[j];
}
b[dq].bh.push_back(i);
sn[++ns] = 'a' + 26;
}
init();
for (int i = 0, dq = 0; i < ns; i++)
if (sn[i] <= 'z')
pd(dq = b[dq].son[sn[i] - 'a']);
else dq = 0;
for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
return 0;
}
|
By 准备退役旅游的 Cansult