ABBYY Cup 3.0

链接:https://codeforces.com/contest/316/problem/G3
思路:一开始想的是原串建立SAM,然后拿各个串去跑SAM,在节点给出贡献,最后沿着fail树统计贡献即可。但是发现一个问题,就是假设跑到了某个点,那么它fail树上的祖先一定是它的子串,它们都应该贡献++,但是当前这个点怎么办?因为一个点是包含了多个串,你怎么知道是从哪个串开始的呢?究其原因是我们子串状态划分的不够细,就会出现这个问题。正解是建立广义后缀自动机,建立的时候标记一下每个点是哪个串的贡献,然后沿fail树统计出现次数。然后我们对于每一个状态进行check,这个状态只要是原串出现过并且满足其他统计串的区间条件即可。复杂度

代码:

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

#define sigma_size 28
using namespace std;
const int maxn = 5e5 + 50010;
const int mod = 1e9 + 7;
typedef long long ll;
int len[maxn * 2];
int f[maxn * 2];
int cnt[maxn * 2];
int ch[maxn * 2][sigma_size];
int idx;
int last;
int epos[maxn * 2];
char s[maxn];
int res[maxn * 2][20];
 
void () {
last = idx = 1;
f[1] = len[1] = 0;
memset(ch[1], 0, sizeof(ch[1]));
}
 
void add(int c, int id) {
int x = ++idx;
len[x] = len[last] + 1;
epos[x] = 1;
res[x][id]++;
int p;
for (p = last; p && !ch[p][c]; p = f[p])ch[p][c] = x;
if (!p)f[x] = 1, cnt[1]++;
else {
int q = ch[p][c];
if (len[p] + 1 == len[q])
f[x] = q, cnt[q]++;
else {
int nq = ++idx;
len[nq] = len[p] + 1;
f[nq] = f[q];
memcpy(ch[nq], ch[q], sizeof(ch[q]));
for (; p && ch[p][c] == q; p = f[p])
ch[p][c] = nq;
f[q] = f[x] = nq;
cnt[nq] += 2;
}
}
last = x;
}
 
int n;
 
void getpos() {
queue<int> q;
for (int i = 1; i <= idx; i++)
if (!cnt[i])q.push(i);
while (!q.empty()) {
int x = q.front();
q.pop();
epos[f[x]] += epos[x];
for(int i = 0; i <= n; i++){
res[f[x]][i] += res[x][i];
}
if (--cnt[f[x]] == 0)q.push(f[x]);
}
}
 
 
typedef pair<int, int> pii;
pii a[20];
#define fi first
#define se second
 
ll ans;
 
int main() {
scanf("%s", s + 1);
n = strlen(s + 1);
init();
for (int i = 1; i <= n; ++i) {
add(s[i] - 'a', 0);
}
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%s %d %d", s + 1, &a[i].fi, &a[i].se);
last = 1;
for(int j = 1, t = strlen(s + 1); j <= t; j++){
add(s[j] - 'a', i);
}
}
getpos();
for (int i = 2; i <= idx; ++i) {
int p = len[i] - len[f[i]];
if(res[i][0] == 0) p = 0;
for (int j = 1; j <= n; ++j) {
if(res[i][j] >= a[j].fi && res[i][j] <= a[j].se) continue;
p = 0;
break;
}
ans += p;
}
printf("%lldn", ans);
return 0;
}