记录编号	617217	评测结果	AAAAAAAAAA
题目名称	[雅礼集训 2017 Day1] 字符串	最终得分	100
用户昵称	RpUtl	是否通过	通过
代码语言	C++	运行时间	1.081 s
提交时间	2026-07-05 19:50:00	内存使用	34.78 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, q, k, l[N], r[N];
int idx = 1, lst = 1, lnk[N], son[N][26], len[N];
int st[N][20], sz[N], pos[N], mx[N];
vector <int> G[N];
string s, t;
void expand(int c) {
	int cur = ++idx;
	sz[cur] = 1;
	len[cur] = len[lst] + 1;
	while (lst && !son[lst][c]) {
		son[lst][c] = cur;
		lst = lnk[lst];
	}
	if (!lst) {
		lnk[cur] = 1;
	} else {
		int p = lst, q = son[lst][c];
		if (len[p] + 1 == len[q]) {
			lnk[cur] = q;
		} else {
			int u = ++idx;
			lnk[u] = lnk[q];
			len[u] = len[p] + 1;
			lnk[q] = lnk[cur] = u;
			for (int i = 0; i < 26; i++) {
				son[u][i] = son[q][i];
			}
			while (p && son[p][c] == q) {
				son[p][c] = u;
				p = lnk[p];
			}
		}
	}
	lst = cur;
	return;
}
void dfs(int x, int fa) {
	st[x][0] = fa;
	for (int i = 1; i <= 19; i++) {
		st[x][i] = st[st[x][i - 1]][i - 1];
	}
	for (auto y : G[x]) {
		dfs(y, x);
		sz[x] += sz[y];
	}
	return;
}
int jump(int x, int L) {
	for (int i = 19; i >= 0; i--) {
		if (len[st[x][i]] >= L) {
			x = st[x][i];
		}
	}
	return x;
}
void work1(){
	int a, b;
	long long ans = 0;
	while(q--) {
		cin >> t >> a >> b;
		t = " " + t, a++, b++, ans = 0;
		int p = 1, nowlen = 0;
		for (int i = 1; i <= k; i++) {
			int c = t[i] - 'a';
			while (p && !son[p][c]) {
				p = lnk[p];
				nowlen = len[p];
			}
			if (!p) p = 1, nowlen = 0;
			else p = son[p][c], nowlen++;
			pos[i] = p, mx[i] = nowlen;
		}
		for (int i = a, L; i <= b; i++) {
			L = r[i] - l[i] + 1; 
			if (mx[r[i]] < L) continue;
			ans += sz[jump(pos[r[i]], L)];
		}
		cout << ans << '\n';
	}
	return;
}
struct ds {
	vector <int> pos;
	void ins(int x) {
		pos.push_back(x);
	}
	int ask(int l, int r) {
		if (!pos.size() || pos.front() > r || pos.back() < l) return 0;
		return upper_bound(pos.begin(), pos.end(), r) - lower_bound(pos.begin(), pos.end(), l);
	}
} w[500][500];
void work2() {
	int a, b;
	long long ans = 0;
	for (int i = 1; i <= m; i++) {
		w[l[i]][r[i]].ins(i);
	}
	while(q--) {
		cin >> t >> a >> b;
		t = " " + t, a++, b++, ans = 0;
		for (int i = 1, p; i <= k; i++) {
			p = 1;
			for (int j = i; j <= k; j++) {
				int c = t[j] - 'a';
				if (!son[p][c]) break;
				p = son[p][c];
				ans += w[i][j].ask(a, b) * sz[p];
			}
		}
		cout << ans << '\n';
	}
	return;
}
int main() {
	freopen("sumstring.in", "r", stdin);
	freopen("sumstring.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m >> q >> k;
	cin >> s; s = " " + s;
	for (int i = 1; i <= n; i++) expand(s[i] - 'a');
	for (int i = 1; i <= m; i++) {
		cin >> l[i] >> r[i];
		l[i]++, r[i]++;
	}
	for (int i = 2; i <= idx; i++) {
		G[lnk[i]].push_back(i);
	}
	dfs(1, 0);
	if (k > 500) work1();
	else work2();
	return 0;
}