今天我刷题了吗
搜索文档…
AC 自动机
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int maxn(1e6 + 10);
7
char s[maxn];
8
int idx, trie[maxn][26];
9
int ext[maxn], fail[maxn];
10
11
template<typename T = int>
12
inline const T read()
13
{
14
T x = 0, f = 1;
15
char ch = getchar();
16
while (ch < '0' or ch > '9') {
17
if (ch == '-') f = -1;
18
ch = getchar();
19
}
20
while (ch >= '0' and ch <= '9') {
21
x = (x << 3) + (x << 1) + ch - '0';
22
ch = getchar();
23
}
24
return x * f;
25
}
26
27
template<typename T>
28
inline void write(T x, bool ln)
29
{
30
if (x < 0) {
31
putchar('-');
32
x = -x;
33
}
34
if (x > 9) write(x / 10, false);
35
putchar(x % 10 + '0');
36
if (ln) putchar(10);
37
}
38
39
void insert(char* str)
40
{
41
int u = 0;
42
for (int i = 0; str[i]; ++i) {
43
int c = str[i] - 'a';
44
if (not trie[u][c]) {
45
trie[u][c] = ++idx;
46
}
47
u = trie[u][c];
48
}
49
++ext[u];
50
}
51
52
void build()
53
{
54
queue<int> q;
55
for (int i = 0; i < 26; ++i) {
56
if (trie[0][i]) {
57
q.push(trie[0][i]);
58
}
59
}
60
while (not q.empty()) {
61
int u = q.front();
62
q.pop();
63
for (int i = 0; i < 26; ++i) {
64
int& v = trie[u][i];
65
if (v) {
66
fail[v] = trie[fail[u]][i];
67
q.push(v);
68
} else {
69
v = trie[fail[u]][i];
70
}
71
}
72
}
73
}
74
75
int query(char* str)
76
{
77
int u = 0, res = 0;
78
for (int i = 0; str[i]; ++i) {
79
int c = str[i] - 'a';
80
u = trie[u][c];
81
for (int j = u; j and compl ext[j]; j = fail[j]) {
82
res += ext[j];
83
ext[j] = -1;
84
}
85
}
86
return res;
87
}
88
89
int main()
90
{
91
#ifndef ONLINE_JUDGE
92
freopen("input.txt", "r", stdin);
93
#endif
94
int n = read();
95
for (int i = 0; i < n; ++i) {
96
scanf("%s", s);
97
insert(s);
98
}
99
build();
100
scanf("%s", s);
101
write(query(s), true);
102
return 0;
103
}
Copied!
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int maxn(160);
7
const int maxl(1e6 + 10);
8
const int maxs(maxn * 80);
9
char s[maxn][maxn], t[maxl];
10
int tot, trie[maxs][26];
11
int idx[maxs], fail[maxs], cnt[maxn];
12
13
template<typename T = int>
14
inline const T read()
15
{
16
T x = 0, f = 1;
17
char ch = getchar();
18
while (ch < '0' or ch > '9') {
19
if (ch == '-') f = -1;
20
ch = getchar();
21
}
22
while (ch >= '0' and ch <= '9') {
23
x = (x << 3) + (x << 1) + ch - '0';
24
ch = getchar();
25
}
26
return x * f;
27
}
28
29
template<typename T>
30
inline void write(T x, bool ln)
31
{
32
if (x < 0) {
33
putchar('-');
34
x = -x;
35
}
36
if (x > 9) write(x / 10, false);
37
putchar(x % 10 + '0');
38
if (ln) putchar(10);
39
}
40
41
void init()
42
{
43
tot = 0;
44
memset(trie, 0, sizeof(trie));
45
memset(fail, 0, sizeof(fail));
46
memset(idx, 0, sizeof idx);
47
memset(cnt, 0, sizeof cnt);
48
}
49
50
void insert(char* str, int id)
51
{
52
int u = 0;
53
for (int i = 1; str[i]; ++i) {
54
int c = str[i] - 'a';
55
if (not trie[u][c]) {
56
trie[u][c] = ++tot;
57
}
58
u = trie[u][c];
59
}
60
idx[u] = id;
61
}
62
63
void build()
64
{
65
queue<int> q;
66
for (int i = 0; i < 26; ++i) {
67
if (trie[0][i]) {
68
q.push(trie[0][i]);
69
}
70
}
71
while (not q.empty()) {
72
int u = q.front();
73
q.pop();
74
for (int i = 0; i < 26; ++i) {
75
int& v = trie[u][i];
76
if (v) {
77
fail[v] = trie[fail[u]][i];
78
q.push(v);
79
} else {
80
v = trie[fail[u]][i];
81
}
82
}
83
}
84
}
85
86
int query(char* str, int n)
87
{
88
int u = 0, res = 0;
89
for (int i = 1; str[i]; ++i) {
90
int c = str[i] - 'a';
91
u = trie[u][c];
92
for (int j = u; j; j = fail[j]) {
93
++cnt[idx[j]];
94
}
95
}
96
for (int i = 1; i <= n; ++i) {
97
res = max(res, cnt[i]);
98
}
99
return res;
100
}
101
102
int main()
103
{
104
#ifndef ONLINE_JUDGE
105
freopen("input.txt", "r", stdin);
106
#endif
107
int n;
108
while (compl scanf("%d", bitand n) and n) {
109
init();
110
for (int i = 1; i <= n; ++i) {
111
scanf("%s", s[i] + 1);
112
insert(s[i], i);
113
}
114
build();
115
scanf("%s", t + 1);
116
int res = query(t, n);
117
write(res, true);
118
for (int i = 1; i <= n; ++i) {
119
if (cnt[i] == res) {
120
puts(s[i] + 1);
121
}
122
}
123
}
124
return 0;
125
}
Copied!
最近更新 11mo ago
复制链接