给定一个模板串SS，多组询问，每次给出一个询问字符串TT和一个区间(l,r)(l,r)

求TT有多少个本质不同的子串没有在SS的[l,r][l,r]这段区间当中出现

∣S∣,∣T∣≤5∗105,∑∣T∣≤106|S|, |T|\le 5*10^5, \sum|T|\le 10^6

LOJ 2720

Solution

首先考虑l=1,r=∣S∣l=1, r=|S|怎么做

答案等于TT中所有本质不同的子串数量减去SS和TT的本质不同公共子串数量

然后考虑如何求SS和TT本质不同公共子串个数

一个很显然的做法就是把 的SAM中每一个状态拿去在 的SAM上跑匹配，但 太大，显然不行

进一步思考，我们发现只需要把每个状态right集合中任取一个右端点所代表的前缀拿去匹配，假设匹配出来的结果为lenlen，则当前状态ii的答案就是区间[0,len]∩[minleni,maxleni][0, len] \cap [\mathrm{minlen}_i, \mathrm{maxlen}_i]中的整数元素个数

于是我们只需要把 的每个前缀拿去匹配即可，这个利用在SAM上做two pointer的方法就能做到

具体来说，假设当前在SAM上的xx点，它匹配上了前缀Ti−1T_{i-1}的长度为lenlen的后缀，新加入一个字符Ti=cT_i = c

如果 有向 的转移，则直接转移过去，len++

否则跳xx的父亲直到有转移或者到根结点，lenlen值相对应改变

这样做相当于一个两个指针在字符串上移动，另外有个节点在SAM上跑，复杂度显然是线性的

接着考虑l,rl, r更一般的做法

大体思路不变，只是每次在SAM上进行转移时，需要保证目标状态所对应的子串在SS的[l,r][l, r]范围内

那么我们只需要判断在目标状态的right集合中是否存在一个右端点pp满足p−len+1≥lp - len + 1\ge l且p≤rp\le r，即p∈[l+len−1,r]p\in[l + len - 1, r]

这个显然直接线段树合并，求出每个状态的right集合，查询区间和是否大于00即可

注意，线段树合并的时候需要新开节点，而不能用之前的。因为以前的题最后只需要根结点的线段树信息，而这里要用到每个节点的线段树信息，所以要动态开点

Code

68pts

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e6 + 100;

int N, M;
char s[Maxn];

struct SAM
{
	int node_cnt, last;
	struct info
	{
		int ch[31], maxlen, fa, pos;
	} node[Maxn << 1];
	vector <int> G[Maxn];

	inline void init ()
	{
		for (int i = 1; i <= node_cnt; ++i)
		{
			node[i].fa = node[i].pos = 0;
			for (int j = 0; j <= 30; ++j) node[i].ch[j] = 0;
		}
		node_cnt = last = 1;
	}

	inline int new_node (int pre, int pos)
	{
		node[++node_cnt].maxlen = node[pre].maxlen + 1;
		node[node_cnt].pos = pos;
		return node_cnt;
	}

	inline void extend (int pos, int c)
	{
		int now = new_node (last, pos), pre = last; last = now;

		for (; pre && !node[pre].ch[c]; pre = node[pre].fa) node[pre].ch[c] = now;

		if (!pre) node[now].fa = 1;
		else
		{
			int x = node[pre].ch[c];
			if (node[x].maxlen == node[pre].maxlen + 1) node[now].fa = x;
			else
			{
				int y = ++node_cnt;
				node[y] = node[x], node[y].maxlen = node[pre].maxlen + 1;
				node[x].fa = node[now].fa = y;
				for (; node[pre].ch[c] == x; pre = node[pre].fa) node[pre].ch[c] = y;
			}
		}
	}

	inline void build (char *S, int n)
	{
		init();
		for (int i = 1; i <= n; ++i) extend (i, S[i] - 'a');
	}
} S, T;

int len[Maxn];

inline void Solve ()
{
	S.build (s, N);

	int Q = read<int>();
	while (Q--)
	{
		scanf("%s", s + 1), M = strlen(s + 1);
		int l = read<int>(), r = read<int>(), now = 1, len_now = 0;
		for (int i = 1; i <= M; ++i)
		{
			int c = s[i] - 'a';
			while (1)
			{
				if (S.node[now].ch[c]) { ++len_now, now = S.node[now].ch[c]; break; }
				else
				{
					if (now == 1) break;
					now = S.node[now].fa;
					len_now = S.node[now].maxlen;
				}
			}
			len[i] = len_now;
		}

		T.build (s, M);
		LL ans = 0;
		for (int i = 1; i <= T.node_cnt; ++i)
		{
			ans += T.node[i].maxlen - T.node[T.node[i].fa].maxlen;
			ans -= max(0, min(T.node[i].maxlen, len[T.node[i].pos]) - T.node[T.node[i].fa].maxlen);
		}

		printf("%lld\n", ans);
	}
}

inline void Input ()
{
	scanf("%s", s + 1), N = strlen(s + 1);
}

int main()
{

	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);

	Input ();
	Solve ();

	return 0;
}

100pts

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1e6 + 100;

int N, M, Root[Maxn << 1];
char s[Maxn];

namespace SEG
{
#define mid (l + r >> 1)
#define ls node[root].ch[0]
#define rs node[root].ch[1]
#define lson ls, l, mid
#define rson rs, mid + 1, r
	int node_cnt;

	struct info
	{
		int cnt, ch[2];
	} node[Maxn * 30];

	inline void push_up (int root) { node[root].cnt = node[ls].cnt + node[rs].cnt; }

	inline void insert (int &root, int l, int r, int x)
	{
		++node[root = ++node_cnt].cnt;
		if (l == r) return ;
		if (x <= mid) insert (lson, x);
		else insert (rson, x);
	}

	inline int merge (int x, int y, int l, int r)
	{
		if (!x || !y) return x | y;
		int root = ++node_cnt;
		ls = merge (node[x].ch[0], node[y].ch[0], l, mid);
		rs = merge (node[x].ch[1], node[y].ch[1], mid + 1, r);
		push_up (root);
		return root;
	}

	inline int query (int root, int l, int r, int x, int y)
	{
		if (x > y) return 0;
		if (x <= l && r <= y) return node[root].cnt;

		int ans = 0;
		if (x <= mid) ans += query (lson, x, y);
		if (y > mid) ans += query (rson, x, y);
		return ans;
	}

#undef mid 
#undef ls 
#undef rs 
#undef lson
#undef rson
}

struct SAM
{
	int node_cnt, last;
	struct info
	{
		int ch[31], maxlen, fa, pos;
	} node[Maxn << 1];
	vector <int> G[Maxn];

	inline void init ()
	{
		for (int i = 1; i <= node_cnt; ++i)
		{
			node[i].fa = node[i].pos = 0;
			for (int j = 0; j <= 30; ++j) node[i].ch[j] = 0;
		}
		node_cnt = last = 1;
	}

	inline int new_node (int pre, int pos, int op)
	{
		node[++node_cnt].maxlen = node[pre].maxlen + 1, node[node_cnt].pos = pos;
		if (op) SEG :: insert (Root[node_cnt], 1, N, pos);
		return node_cnt;
	}

	inline void extend (int pos, int c, int op)
	{
		int now = new_node (last, pos, op), pre = last; last = now;

		for (; pre && !node[pre].ch[c]; pre = node[pre].fa) node[pre].ch[c] = now;

		if (!pre) node[now].fa = 1;
		else
		{
			int x = node[pre].ch[c];
			if (node[x].maxlen == node[pre].maxlen + 1) node[now].fa = x;
			else
			{
				int y = ++node_cnt;
				node[y] = node[x], node[y].maxlen = node[pre].maxlen + 1;
				node[x].fa = node[now].fa = y;
				for (; node[pre].ch[c] == x; pre = node[pre].fa) node[pre].ch[c] = y;
			}
		}
	}

	inline void dfs (int x)
	{
		for (int i = 0; i < G[x].size(); ++i)
		{
			int y = G[x][i];
			dfs (y);
			Root[x] = SEG :: merge (Root[x], Root[y], 1, N);
		}
	}

	inline void build (char *S, int n, int op)
	{
		init ();
		for (int i = 1; i <= n; ++i) extend (i, S[i] - 'a', op);
		if (op)
		{
			for (int i = 1; i <= node_cnt; ++i) G[node[i].fa].pb (i);
			dfs (1);
		}
	}
} S, T;

int len[Maxn];

inline void Solve ()
{
	S.build (s, N, 1);

	int Q = read<int>();
	while (Q--)
	{
		scanf("%s", s + 1), M = strlen(s + 1);
		int l = read<int>(), r = read<int>(), now = 1, len_now = 0;
		for (int i = 1; i <= M; ++i)
		{
			int c = s[i] - 'a';
			while (1)
			{
				if (SEG :: query (Root[S.node[now].ch[c]], 1, N, l + len_now, r)) { ++len_now, now = S.node[now].ch[c]; break; }
				else
				{
					if (now == 1) break;
					--len_now;
					if (len_now == S.node[S.node[now].fa].maxlen) now = S.node[now].fa;
				}
			}
			len[i] = len_now;
		}

		T.build (s, M, 0);
		LL ans = 0;
		for (int i = 1; i <= T.node_cnt; ++i)
		{
			ans += T.node[i].maxlen - T.node[T.node[i].fa].maxlen;
			ans -= max(0, min(T.node[i].maxlen, len[T.node[i].pos]) - T.node[T.node[i].fa].maxlen);
		}

		printf("%lld\n", ans);
	}
}

inline void Input ()
{
	scanf("%s", s + 1), N = strlen(s + 1);
}

int main()
{

	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);

	Input ();
	Solve ();

	return 0;
}