P3966-[TJOI2013]单词
题目:
题目描述:
小张最近在忙毕设,所以一直在读论文。一篇论文是由许多单词组成但小张发现一个单词会在论文中出现很多次，他想知道每个单词分别在论文中出现了多少次。
输入格式:
第一行一个整数 $N$，表示有 $N$ 个单词。
接下来 $N$ 行每行一个单词,每个单词都由小写字母 $a-z$ 组成。
输出格式:
输出 $N$ 个整数,第 $i$ 行的数表示第 $i$ 个单词在文章中出现了多少次。
样例:
样例输入1:
样例输出1:
思路:
实现:
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
| // Problem: P3966 [TJOI2013]单词
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3966
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
const int maxn = 1e6 + 1e5 + 10;
int n, a[maxn], h[maxn], cnt, last, ch[maxn][26], sz[maxn], fail[maxn];
char s[maxn];
struct ac
{
void ins(int x)
{
yin >> (s + 1);
int now = 0, len = strlen(s + 1);
for (int i = 1; i <= len; i++)
{
int u = s[i] - 'a';
if (!ch[now][u])
ch[now][u] = ++cnt;
now = ch[now][u];
sz[now]++;
}
a[x] = now;
}
void build()
{
int i, head = 0, tail = 0;
for (i = 0; i < 26; i++)
if (ch[0][i])
h[++tail] = ch[0][i];
while (head < tail)
{
int x = h[++head], y;
for (i = 0; i < 26; i++)
if (y = ch[x][i])
{
h[++tail] = y;
fail[y] = ch[fail[x]][i];
}
else
ch[x][i] = ch[fail[x]][i];
}
}
void solve()
{
for (int i = cnt; i >= 0; i--)
sz[fail[h[i]]] += sz[h[i]];
for (int i = 1; i <= n; i++)
yout << sz[a[i]] << endl;
}
} ac;
int main()
{
//freopen("word.in","r",stdin);
//freopen("word.out","w",stdout);
yin >> n;
for (int i = 1; i <= n; i++)
ac.ins(i);
ac.build();
ac.solve();
return 0;
}
|