代码

#include <vector>
#include <set>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <queue>

#define pb push_back
#define fi first
#define se second
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(a) a.begin(), a.end()
#define lowbit(x) ((x) & -(x))

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, int> pii;
typedef pair<int, int> pi;
typedef vector<int> VI;

namespace io {
	const int L = (1 << 21) + 1;
	char ibuf[L], *iS, *iT, obuf[L], *oS = obuf, *oT = obuf + L - 1, c, qu[55]; int f, qr;
	#define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, L, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () { fwrite (obuf, 1, oS - obuf, stdout); oS = obuf; }
	inline void putc (char x) { *oS ++ = x; if (oS == oT) flush (); }
	template <class I> inline void gi (I & x) {
		for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
		for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= f;
	}
	template <class I> inline void print (I x) {
		if (!x) putc ('0'); if (x < 0) putc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0', x /= 10;
		while (qr) putc (qu[qr --]);
	}
	inline char read () {
		for (c = gc(); c < 'a' || c > 'z'; c = gc());
		return c;
	}
	inline void gs (char *s) {
		int l;
		for (c = gc(); c < 'a' || c > 'z'; c = gc());
		for (l = 0; c <= 'z' && c >= 'a'; c = gc()) s[l] = c, ++l;
		s[l] = 0;
	}
	inline void ps (const char *s) {
		int l = strlen(s), i;
		for (i = 0; i < l; i ++) putc(s[i]);
	}
	struct IOC { ~ IOC () { flush (); } } _ioc_;
} ;
using io::gi;
using io::gs;
using io::ps;
using io::putc;
using io::read;
using io::print;

template <class T> inline bool chkmin(T &a, T b) { return b < a ? a = b, true : false; }
template <class T> inline bool chkmax(T &a, T b) { return a < b ? a = b, true : false; }

namespace fast {
	const int N = 1600005;
	int x[N], m, m1[N], m2[N], m3[N], *rk = m1, *sa = m2, *y = m3;
	void SA (int *str, int n, int *height, int *rank) {
		int i, j, l;
		for (i = 1; i <= n; i ++) x[rk[i] = str[i]] ++, chkmax(m, str[i]);
		for (i = 1; i <= m; i ++) x[i] += x[i - 1];
		for (i = n; i >= 1; i --) sa[x[rk[i]]--] = i;
		for (l = 1; l <= n; l <<= 1) {
			for (i = n - l + 1; i <= n; i ++) y[++x[rk[i]]] = i;
			for (i = 1; i <= n; i ++) if (sa[i] > l) j = sa[i] - l, y[++x[rk[j]]] = j;
			swap (sa, y);
			x[m = y[sa[1]] = 1] = 0;
			for (i = 2; i <= n; i ++) {
				if (rk[sa[i]] != rk[sa[i - 1]] || (sa[i] + l <= n ? rk[sa[i] + l] : -1) != (sa[i - 1] + l <= n ? rk[sa[i - 1] + l] : -1)) x[++m] = i - 1;
				y[sa[i]] = m;
			}
			swap (rk, y);
			if (m == n) break;
		}
		j = 0;
		for (i = 1; i <= n; i ++) {
			while (str[i + j] == str[sa[rk[i] - 1] + j]) j ++;
			height[rank[i] = rk[i]] = j, j -= !!j;
		}
	}
}

const int N = 500005, M = 1600005, L = 100005, G = 25;

namespace ds {
	const int M = 12345678;
	int ls[M], rs[M], cnt[M], ec;
	int copynode(int u){
		++ec, ls[ec] = ls[u], rs[ec] = rs[u], cnt[ec] = cnt[u];
		return ec;
	}
	void modify(int &u, int l, int r, int p){
		u = copynode(u), ++cnt[u];
		if (l == r) return ;
		int mid = (l + r) >> 1;
		p <= mid ? modify(ls[u], l, mid, p) : modify(rs[u], mid + 1, r, p);
	}
	bool query(int x, int y, int l, int r, int s, int t){
		if (cnt[x] == cnt[y]) return false;
		if (l == s && r == t) return true;
		int mid = (l + r) >> 1;
		if (t <= mid) return query(ls[x], ls[y], l, mid, s, t);
		if (s > mid) return query(rs[x], rs[y], mid + 1, r, s, t);
		return query(ls[x], ls[y], l, mid, s, mid) || query(rs[x], rs[y], mid + 1, r, mid + 1, t);
	}
}

char str[N];
int n, m, q, ch[M], us[L], vs[L], ut[L], vt[L], rk[M], sa[M], f[G][M], lg[M], ff[M], rt[M];
ll res;
vector <int> ID;

int rmq (int u, int v) {
	int d = lg[v - u + 1];
	return min(f[d][u], f[d][v - (1 << d) + 1]);
}
int lcp (int u, int v) {
	if (u == -1 || v == -1) return -N;
	if (u == v) return n - u + 1;
	u = rk[u], v = rk[v];
	if (u > v) swap(u, v);
	return rmq(u + 1, v);
}

bool cmp(const int &x, const int &y){ return rk[x] < rk[y]; }

int fndl (int u, int len) {
	int l = 1, r = u, mid = (l + r) >> 1;
	while (l < r) {
		if (rmq(mid + 1, u) >= len) r = mid;
		else l = mid + 1;
		mid = (l + r) >> 1;
	}
	return mid;
}
int fndr (int u, int len) {
	int l = u, r = m, mid = (l + r + 1) >> 1;
	while (l < r) {
		if (rmq(u + 1, mid) >= len) l = mid;
		else r = mid - 1;
		mid = (l + r + 1) >> 1;
	}
	return mid;
}

bool chk (int l, int r, int s, int t) {
	int len = t - s + 1, a, b;
	if (len > r - l + 1) return false;
	a = fndl(rk[s], len), b = fndr(rk[s], len);
	return ds::query(rt[b], rt[a - 1], 1, n, l, r - len + 1);
}

int main(){
	freopen("name.in", "r", stdin), freopen("name.out", "w", stdout);
	int l, r, i, j, k;
	gs(str + 1), n = strlen(str + 1);
	for (i = 1; i <= n; i ++) ch[++m] = str[i] - 'a' + 1;
	gi(q);
	for (i = 1; i <= q; i ++) {
		ch[++m] = i + 26;
		gs(str + 1), l = strlen(str + 1), gi(us[i]), gi(vs[i]);
		for (ut[i] = m + 1, j = 1; j <= l; j ++) ch[++m] = str[j] - 'a' + 1;
		vt[i] = m;
	}
	fast :: SA (ch, m, f[0], rk);
	for (i = 1; i <= m; i ++) sa[rk[i]] = i;
	for (i = 2; i <= m; i ++) lg[i] = lg[i - 1] + !(i & i - 1);
	for (l = 2, i = 1; l <= m; l <<= 1, i ++) for (j = 1; j <= m - l + 1; j ++)
		f[i][j] = min(f[i - 1][j], f[i - 1][j + (l >> 1)]);
	for (i = 1; i <= m; i ++) {
		rt[i] = rt[i - 1]; 
		if (sa[i] <= n) ds::modify(rt[i] = rt[i - 1], 1, n, sa[i]);
	} 
	for (i = 1; i <= q; i ++) {
		for (l = ut[i], r = ut[i] - 1; l <= vt[i]; ++l) {
			chkmax(r, l - 1);
			while (r < vt[i] && chk(us[i], vs[i], l, r + 1)) ++r;
			ff[l] = r - l + 1;
		}
		ID.resize(vt[i] - ut[i] + 1);
		for (j = ut[i]; j <= vt[i]; j ++) ID[j - ut[i]] = j;
		sort(ID.begin(), ID.end(), cmp);
		for (j = 1; j < ID.size(); j ++) chkmax(ff[ID[j]], lcp(ID[j - 1], ID[j]));
		res = (ll)(vt[i] - ut[i] + 2) * (vt[i] - ut[i] + 1) / 2; 
		for (j = ut[i]; j <= vt[i]; j ++) res -= ff[j];
		print(res), putc('\n');
	}
	return 0;
}

评测结果