Loj 6031 字符串

Posted on | Edited on | Views:

SAM + 根号分治.

每次询问的 $k$ 都是一样的,可以记一个常数 $p=kq$ ,考虑根号分治,对 $k\le q$ 和 $k>q$ 两种情况讨论.

$k\le q$

每次询问的串长不会超过 $\sqrt p$ ,可以直接枚举 $w$ 的每个子串 $w[l,r]$ .

算出这个子串在 $s$ 中出现的次数,再乘上 $[l,r]$ 这个区间在第 $a$ 到第 $b$ 个区间出现的次数,就是这个子串对询问贡献.

前者可以在串 $s$ 的 SAM 上找出 $w[l,r]$ 对应的状态,其 right 集合大小即为出现次数.

后者可以将 $[l,r]$ 在 $m$ 个区间中出现的所有位置存在 vector 中,二分找出 $a,b$ 的位置,做差即为所求.

时间复杂度 $O(qk^2\log m)=O(p\sqrt p \log m)$ .

$k> q$

询问的次数不超过 $\sqrt p$ ,对于每次询问,我们都将第 $a$ 个区间到第 $b$ 个区间拿出来,考虑每个区间 $[l,r]$ 的贡献.

$w[l,r]$ 在串 $s$ 中出现的次数等价于 $s$ 有多少个前缀与 $w[1,r]$ 的 LCS 长度不小于 $r-l+1$ .

将 $w[1,r]$ 在 SAM 上对应的位置找出,倍增查找出其深度最浅的满足 $maxlen\ge r-l+1$ 的祖先.

其 right 集合大小即为所求.

注意在给 $w[1,r]$ 定位时,若沿着失配边往回跳,有效的后缀长度就会改变.

时间复杂度 $O(q(k+m\log n))=O(p+m\sqrt p\log n)$ .

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
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
const int N = 2e5 + 10, S = 26, K = 320;
int fa[N], len[N], siz[N], ch[N][S], idx = 1, lst = 1;
void Extend(int c)
{
	int p = lst, np = ++idx;
	lst = np;
	len[np] = len[p] + 1, siz[np] = 1;
	while (p && !ch[p][c])
		ch[p][c] = np, p = fa[p];
	if (!p)
		fa[np] = 1;
	else
	{
		int q = ch[p][c];
		if (len[q] == len[p] + 1)
			fa[np] = q;
		else
		{
			int nq = ++idx;
			len[nq] = len[p] + 1;
			fa[nq] = fa[q];
			fa[q] = fa[np] = nq;
			memcpy(ch[nq], ch[q], sizeof ch[nq]);
			while (p && ch[p][c] == q)
				ch[p][c] = nq, p = fa[p];
		}
	}
}
int A[N], t[N];
void toposort()
{
	for (int i = 1; i <= idx; ++i)
		++t[len[i]];
	for (int i = 1; i <= idx; ++i)
		t[i] += t[i - 1];
	for (int i = 1; i <= idx; ++i)
		A[t[len[i]]--] = i;
}
char s[N], w[N];
int n, m, q, k, L[N], R[N];
namespace Case1
{
	vector<int> vc[K][K];
	int calc(int a, int b, int l, int r)
	{
		int x = lower_bound(vc[l][r].begin(), vc[l][r].end(), a) - vc[l][r].begin();
		int y = upper_bound(vc[l][r].begin(), vc[l][r].end(), b) - vc[l][r].begin() - 1;
		return y - x + 1;
	}
	void solve()
	{
		for (int i = 1; i <= m; ++i)
			if (1 <= L[i] && L[i] <= R[i] && R[i] <= k)
				vc[L[i]][R[i]].push_back(i);
		while (q--)
		{
			scanf("%s", w + 1);
			int a = read() + 1, b = read() + 1;
			ll ans = 0;
			for (int l = 1; l <= k; ++l)
			{
				int x = 1;
				for (int r = l; r <= k; ++r)
				{
					x = ch[x][w[r] - 'a'];
					if (!siz[x])
						break;
					if (vc[l][r].empty())
						continue;
					if (vc[l][r].back() < a || vc[l][r].front() > b)
						continue;
					ans += 1LL * siz[x] * calc(a, b, l, r);
				}
			}
			printf("%lld\n", ans);
		}
	}
}
namespace Case2
{
	const int D = 18;
	int Fa[N][D], dep[N];
	vector<int> tmp[N];
	int query(int x, int bound)
	{
		if (len[x] < bound)
			return 0;
		for (int i = D - 1; i >= 0; --i)
			if ((1 << i) <= dep[x] && len[Fa[x][i]] >= bound)
				x = Fa[x][i];
		return siz[x];
	}
	int tot[N];
	void solve()
	{
		for (int i = 2; i <= idx; ++i)
		{
			int x = A[i];
			dep[x] = dep[fa[x]] + 1, Fa[x][0] = fa[x];
			for (int j = 1; (1 << j) <= dep[x]; ++j)
				Fa[x][j] = Fa[Fa[x][j - 1]][j - 1];
		}
		while (q--)
		{
			scanf("%s", w + 1);
			int a = read() + 1, b = read() + 1;
			for (int i = a; i <= b; ++i)
				tmp[R[i]].push_back(L[i]);
			ll ans = 0;
			int x = 1, cnt = 0;
			for (int r = 1; r <= k; ++r)
			{
				int c = w[r] - 'a';
				if (ch[x][c])
				{
					x = ch[x][c];
					++cnt;
				}
				else
				{
					while (x && !ch[x][c])
						x = fa[x];
					if (!x)
						x = 1, cnt = 0;
					else
						cnt = len[x] + 1, x = ch[x][c];
				}
				for (int l : tmp[r])
					if (cnt >= r - l + 1)
						ans += query(x, r - l + 1);
			}
			printf("%lld\n", ans);
			for (int i = a; i <= b; ++i)
				tmp[R[i]].clear();
		}
	}
}
int main()
{
	n = read(), m = read(), q = read(), k = read();
	scanf("%s", s + 1);
	for (int i = 1; i <= n; ++i)
		Extend(s[i] - 'a');
	toposort();
	for (int i = idx; i >= 2; --i)
		siz[fa[A[i]]] += siz[A[i]];
	for (int i = 1; i <= m; ++i)
		L[i] = read() + 1, R[i] = read() + 1;
	if (k <= q)
		Case1::solve();
	else
		Case2::solve();
	return 0;
}