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
| #include <iostream>
#include <cstring>
#define maxm 11
#define maxn 550010
#define Maxn 1100010
#define ll long long
using namespace std;
struct SAM {
int nxt[26], l, L;
} T[Maxn]; int f[Maxn], top, rt, last;
void init_SAM() {
for (int i = 1; i <= top; ++i) {
T[i].L = T[i].l = f[i] = 0;
fill(T[i].nxt, T[i].nxt + 26, 0);
} rt = top = last = 1;
T[1].L = 0;
}
int extend(int p, int ch) {
if (T[p].nxt[ch]) {
int q = T[p].nxt[ch], nq;
if (T[q].L - 1 == T[p].L) return q;
nq = ++top; T[nq].L = T[p].L + 1; f[nq] = f[q];
memcpy(T[nq].nxt, T[q].nxt, sizeof T[q].nxt);
while (p && T[p].nxt[ch] == q) T[p].nxt[ch] = nq, p = f[p];
f[q] = nq; return nq;
}
int np = ++top; T[np].L = T[p].L + 1;
while (p && !T[p].nxt[ch]) T[p].nxt[ch] = np, p = f[p];
if (!p) return f[np] = rt, np;
int q = T[p].nxt[ch];
if (T[q].L - 1 == T[p].L) f[np] = q;
else {
int nq = ++top; T[nq].L = T[p].L + 1;
f[nq] = f[q]; memcpy(T[nq].nxt, T[q].nxt, sizeof T[q].nxt);
while (p && T[p].nxt[ch] == q) T[p].nxt[ch] = nq, p = f[p];
f[np] = f[q] = nq;
} return np;
}
void insert(char *s) {
int l = strlen(s), p = rt;
for (int i = 0; i < l; ++i) p = extend(p, s[i] - 'a');
}
int tax[maxn], tp[Maxn];
void rsort(int n) {
for (int i = 1; i <= n; ++i) tax[i] = 0;
for (int i = 1; i <= top; ++i) ++tax[T[i].L];
for (int i = 1; i <= n; ++i) tax[i] += tax[i - 1];
for (int i = 1; i <= top; ++i) tp[tax[T[i].L]--] = i;
for (int i = top, u = tp[i]; i > 1; u = tp[--i]) T[u].l = T[f[u]].L + 1;
}
bool ok[Maxn]; int cnt[Maxn];
int n, m, pos[maxn], l[maxm], r[maxm];
char s[maxn], t[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> s + 1 >> m; int n = strlen(s + 1), L = n;
init_SAM(), insert(s + 1);
for (int i = 1; i <= m; ++i) {
cin >> t + pos[i] >> l[i] >> r[i];
pos[i + 1] = pos[i] + strlen(t + pos[i]);
insert(t + pos[i]); L = max(L, pos[i + 1] - pos[i]);
} rsort(L);
for (int i = 1, now = rt; i <= n; ++i) {
now = T[now].nxt[s[i] - 'a'];
ok[now] = true;
}
for (int i = top, u = tp[i]; i > 1; u = tp[--i]) if (f[u] != rt) ok[f[u]] |= ok[u];
for (int o = 1; o <= m; ++o) {
for (int i = 1; i <= top; ++i) cnt[i] = 0;
for (int i = pos[o], now = rt; i < pos[o + 1]; ++i) {
now = T[now].nxt[t[i] - 'a'];
++cnt[now];
}
for (int i = top, u = tp[i]; i > 1; u = tp[--i]) if (f[u] != rt) cnt[f[u]] += cnt[u];
for (int i = 1; i <= top; ++i)
if (cnt[i] < l[o] || r[o] < cnt[i]) ok[i] = 0;
} ll ans = 0;
for (int i = 2; i <= top; ++i) if (ok[i]) ans += T[i].L - T[i].l + 1;
cout << ans << "\n";
return 0;
}
|