代码

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 500000, maxc = 1000000, maxv = 30000000;
char s[maxn + 10];
int n, q, ch[maxc + 10][26], fa[maxc + 10], rt[maxn + 10];
int dfn[maxc + 10], ed[maxc + 10], dfscnt;
int maxl[maxc + 10], np = 1, ndcnt = 1, lim[maxc + 10];
bool islv[maxc + 10];
vector<int> g[maxc + 10];

void add(int c) {
	int p = np; np = ++ndcnt; islv[np] = 1;
	maxl[np] = maxl[p] + 1;
	while (p && !ch[p][c]) {
		ch[p][c] = np; p = fa[p];
	}
	if (p) {
		int q = ch[p][c];
		if (maxl[p] + 1 == maxl[q]) fa[np] = q;
		else {
			int nq = ++ndcnt; fa[nq] = fa[q];
			fa[q] = fa[np] = nq; maxl[nq] = maxl[p] + 1;
			for (int i = 0; i < 26; ++i) ch[nq][i] = ch[q][i];
			while (ch[p][c] == q) {
				ch[p][c] = nq; p = fa[p];
			}
		}
	} else fa[np] = 1;
}

int lc[maxv + 10], rc[maxv + 10], sz[maxv + 10], vcnt;

void build(int &p, int ls, int rs) {
	p = ++vcnt;
	if (ls != rs) {
		int mid = ls + rs >> 1;
		build(lc[p], ls, mid); build(rc[p], mid + 1, rs);
	}
}

void add(int &p, int cmp, int k, int ls, int rs) {
	p = ++vcnt; lc[p] = lc[cmp]; rc[p] = rc[cmp]; sz[p] = sz[cmp] + 1;
	if (ls != rs) {
		int mid = ls + rs >> 1;
		if (k <= mid) add(lc[p], lc[cmp], k, ls, mid);
		else add(rc[p], rc[cmp], k, mid + 1, rs);
	}
}

int query(int p, int l, int r, int ls, int rs) {
	if (l > r) return 0;
	if (l == ls && r == rs) return sz[p];
	else {
		int mid = ls + rs >> 1;
		if (r <= mid) return query(lc[p], l, r, ls, mid);
		else if (l > mid) return query(rc[p], l, r, mid + 1, rs);
		else return query(lc[p], l, mid, ls, mid) + query(rc[p], mid + 1, r, mid + 1, rs);
	}
}


void dfs(int p) {
	dfn[p] = dfscnt;
	if (islv[p]) {
		++dfscnt; add(rt[dfscnt], rt[dfscnt - 1], maxl[p], 1, n);
	}
	for (int i = 0; i < g[p].size(); ++i) dfs(g[p][i]);
	ed[p] = dfscnt;
}


namespace anothersam {

	int n, q, ch[maxc * 2 + 10][26], fa[maxc * 2 + 10], maxl[maxc * 2 + 10], np, ndcnt;
	int pos[maxc * 2 + 10];

	void init() {
		for (int i = 1; i <= ndcnt; ++i) {
			for (int j = 0; j < 26; ++j) ch[i][j] = 0;
			fa[i] = maxl[i] = pos[i] = 0;
		}
		np = ndcnt = 1;
	}

	void add(int c) {
		int p = np; np = ++ndcnt; 
		maxl[np] = pos[np] = maxl[p] + 1;
		while (p && !ch[p][c]) {
			ch[p][c] = np; p = fa[p];
		}
		if (p) {
			int q = ch[p][c];
			if (maxl[p] + 1 == maxl[q]) fa[np] = q;
			else {
				int nq = ++ndcnt; fa[nq] = fa[q]; pos[nq] = pos[q];
				fa[q] = fa[np] = nq; maxl[nq] = maxl[p] + 1;
				for (int i = 0; i < 26; ++i) ch[nq][i] = ch[q][i];
				while (ch[p][c] == q) {
					ch[p][c] = nq; p = fa[p];
				}
			}
		} else fa[np] = 1;
	}

	ll calc() {
		ll ans = 0;
		for (int i = 2; i <= ndcnt; ++i)
			ans += max(0, maxl[i] - max(maxl[fa[i]], lim[pos[i]]));
		return ans;
	}
}

int main() {
	scanf("%s", s + 1); n = strlen(s + 1);
	for (int i = 1; i <= n; ++i) add(s[i] - 'a');
	for (int i = 2; i <= ndcnt; ++i) g[fa[i]].push_back(i);
	build(rt[0], 1, n);
	dfs(1);
	scanf("%d", &q);
	while (q--) {
		int l, r, p = 1, nowl = 0;
		scanf("%s%d%d", s + 1, &l, &r); int len = strlen(s + 1);
		anothersam::init();
		for (int i = 1; i <= len; ++i) {
			int c = s[i] - 'a';
			anothersam::add(c);
			while (1) {
				if (ch[p][c]) {
					int e = ch[p][c];
					if (query(rt[ed[e]], l + nowl, r, 1, n) - query(rt[dfn[e]], l + nowl, r, 1, n)) {
						++nowl; p = e; break;
					}
				}
				if (nowl == 0) break;
				--nowl; if (nowl == maxl[fa[p]]) p = fa[p];
			}
			lim[i] = nowl;
		}
		printf("%lld\n", anothersam::calc());
	}
}

评测结果