[题解] [TJOI2013] 单词

[题解] [TJOI2013] 单词

一篇论文是由许多单词组成,但小张发现一个单词会在论文中出现很多次,问每个单词分别在论文中出现了多少次。

$1\le n \le 200$,单词总长度不超过 $10^6$

题目链接


思路

很容易理解的广义 SAM 做法(不会的可以戳 这里),把所有的单词建成一个广义 SAM,然后记录一下每个单词的末尾对应的 SAM 上的节点,最后统一处理一下 cnt 然后输出即可。

代码

mivik.h

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
// Mivik 2020.8.20
#include <mivik.h>

MI cin;

const int $s = 201;
const int $n = 1000001;
const int S = $n << 1;
const int $c = 26;

template<typename T> inline bool gmax(T& a, const T& b) { return a < b && (a = b, true); }

namespace sam {
int tar[S][$c], pre[S], len[S], cnt[S], too[$n], seq[S], n;
int lst = 1, tot = 1;
inline int node(int l) { len[++tot] = l; return tot; }
inline void extend(int c) {
int i = lst; int &op = tar[i][c]? lst: pre[lst = node(len[i] + 1)];
while (!tar[i][c]) { tar[i][c] = lst; if (!(i = pre[i])) return (void)(op = 1); }
const int o = tar[i][c]; if (len[i] + 1 == len[o]) return (void)(op = o);
const int s = node(len[i] + 1); memcpy(tar[s], tar[o], sizeof(tar[0]));
pre[s] = pre[o]; op = pre[o] = s;
do { tar[i][c] = s; i = pre[i]; } while (i && tar[i][c] == o);
}
inline void work() {
for (int i = 1; i <= tot; ++i) ++too[len[i]];
for (int i = 1; i <= n; ++i) too[i] += too[i - 1];
for (int i = 1; i <= tot; ++i) seq[too[len[i]]--] = i;
for (int i = tot; i > 1; --i) {
const int x = seq[i];
cnt[pre[x]] += cnt[x];
}
}
} // namespace sam
int pos[$s];
int main() {
const int n = R;
for (int i = 1; i <= n; ++i) {
char c = cin.read<char>();
sam::lst = 1;
while (c != -1 && !isspace(c)) {
sam::extend(c - 'a');
++sam::cnt[sam::lst];
c = cin.get();
}
gmax(sam::n, sam::len[sam::lst]);
pos[i] = sam::lst;
}
sam::work();
for (int i = 1; i <= n; ++i) cout < sam::cnt[pos[i]] < endl;
}
作者

Mivik

发布于

2020-08-23

更新于

2021-05-31

许可协议

评论