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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
| #include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 1e6+5;
int n, q;
int root[N], val[N<<6], tot, ls[N<<6], rs[N<<6];
void add(int &x, int l, int r, int pos)
{
if(!x) x = ++tot; val[x] |= 1;
if(l == r) return;
int mid = (l+r)>>1;
if(pos <= mid) return add(ls[x], l, mid, pos);
else return add(rs[x], mid+1, r, pos);
}
bool query(int x, int l, int r, int ql, int qr)
{
if(ql > qr) return false;
if(!x||(ql <= l&&r <= qr)) return val[x];
int mid = (l+r)>>1;
if(ql <= mid&&query(ls[x], l, mid, ql, qr)) return true;
if(qr > mid&&query(rs[x], mid+1, r, ql, qr)) return true;
return false;
}
int merge(int x, int y)
{
if(!x||!y) return x|y;
int z = ++tot;
val[z] = val[x]|val[y];
ls[z] = merge(ls[x], ls[y]);
rs[z] = merge(rs[x], rs[y]);
return z;
}
char s[N];
struct Sam
{
int tot = 1, last = 1, ch[N][26], fa[N], len[N], ac[20][N], w[N];
int64 ans;
int tax[N], p[N];
void clear()
{
for(int i = 1; i <= tot; ++i)
memset(ch[i], 0, sizeof(ch[i])),
fa[i] = w[i] = tax[i] = 0;
tot = 1, last = 1, ans = 0;
}
void insert(int c, int val = -1)
{
int cur = ++tot, pre = last; last = cur;
len[cur] = len[pre]+1;
if(val == -1) add(root[cur], 1, n, len[cur]); else w[cur] = val;
while(pre&&!ch[pre][c]) ch[pre][c] = cur, pre = fa[pre];
if(!pre) return void(fa[cur] = 1);
int x = ch[pre][c];
if(len[pre]+1 == len[x]) return void(fa[cur] = x);
int y = ++tot; len[y] = len[pre]+1; fa[y] = fa[x]; fa[x] = fa[cur] = y;
memcpy(ch[y], ch[x], sizeof(ch[x]));
while(pre&&ch[pre][c] == x) ch[pre][c] = y, pre = fa[pre];
}
void build(int type = 1)
{
for(int i = 1; i <= tot; ++i) ++tax[len[i]];
for(int i = 1; i <= tot; ++i) tax[i] += tax[i-1];
for(int i = 1; i <= tot; ++i) p[tax[len[i]]--] = i;
for(int i = tot; i > 1; --i)
{
int x = p[i];
if(type) root[fa[x]] = merge(root[fa[x]], root[x]);
else
{
w[fa[x]] = max(w[x], w[fa[x]]);
ans += max(0, len[x]-max(w[x], len[fa[x]]));
}
}
if(type)
{
for(int i = 1; i <= tot; ++i)
{
int x = p[i]; ac[0][x] = fa[x];
for(int k = 1; k < 20; ++k) ac[k][x] = ac[k-1][ac[k-1][x]];
}
}
}
int find(int x, int d)
{
for(int i = 19; ~i; --i) if(len[ac[i][x]] >= d) x = ac[i][x];
return x;
}
int get(int x, int ql, int qr, int lcs)
{
if(query(root[x], 1, n, ql+lcs-1, qr)) return lcs;
int ret = 0, l = 1, r = lcs-1;
while(l <= r)
{
int mid = (l+r)>>1;
if(query(root[find(x, mid)], 1, n, ql+mid-1, qr)) ret = mid, l = mid+1;
else r = mid-1;
}
return ret;
}
}sam, buf;
int main()
{
scanf("%s", s); q = read(); n = strlen(s);
for(int i = 0; s[i]; ++i) sam.insert(s[i]-'a'); sam.build();
while(q--)
{
scanf("%s", s); int l = read(), r = read();
int x = 1, lcs = 0; buf.clear();
for(int i = 0; s[i]; ++i)
{
while(x&&!sam.ch[x][s[i]-'a']) x = sam.fa[x], lcs = sam.len[x];
if(!x) x = 1, lcs = 0;
else x = sam.ch[x][s[i]-'a'], ++lcs;
buf.insert(s[i]-'a', sam.get(x, l, r, lcs));
}
buf.build(0);
printf("%lld\n", buf.ans);
}
return 0;
}
|