代码

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 500032;

char S[N], T[N];
int go[N][26], par[N], len[N], cnt = 1, p = 1, n;

void extend(int c) {
	int np = ++cnt;
	len[np] = len[p] + 1;
	for (; p && !go[p][c]; p = par[p]) go[p][c] = np;
	if (!p) par[np] = 1;
	else {
		int q = go[p][c];
		if (len[q] == len[p] + 1) par[np] = q;
		else {
			int nq = ++cnt;
			par[nq] = par[q];
			len[nq] = len[p] + 1;
			memcpy(go[nq], go[q], sizeof *go);
			for (; p && go[p][c] == q; p = par[p]) go[p][c] = nq;
			par[np] = par[q] = nq;
		}
	}
	p = np;
}

int a[N], b[N], c[N], sa[N];
void SA() {
	int *x = a, *y = b, m = 26;
	memset(c+1, 0, 26*sizeof(int));
	for (int i = 1; i <= n; i++) c[x[i] = T[n-i] ^ '`']++;
	for (int i = 1; i < m; i++) c[i+1] += c[i];
	for (int i = 1; i <= n; i++) sa[c[x[i]]--] = i;
	for (int k = 1; k <= n; k <<= 1) {
		int p = 0;
		for (int i = n-k+1; i <= n; i++) y[++p] = i;
		for (int i = 1; i <= n; i++)
			if (sa[i] > k) y[++p] = sa[i] - k;
		memset(c+1, 0, m*sizeof(int));
		for (int i = 1; i <= n; i++) c[x[i]]++;
		for (int i = 1; i < m; i++) c[i+1] += c[i];
		for (int i = n; i > 0; i--) sa[c[x[y[i]]]--] = y[i];
		std::swap(x, y);
		int u = sa[1];
		x[u] = p = 1;
		for (int i = 2, v = sa[2]; i <= n; u = v, v = sa[++i])
			x[v] = y[u]==y[v] && y[u+k]==y[v+k] ? p : ++p;
		if ((m = p) >= n) break;
	}
}

int rk[N], h[N];
void Height() {
	for (int i = 1; i <= n; i++) rk[sa[i]] = i;
	for (int i = 1, k = 0; i <= n; i++) {
		if (k) k--;
		if (rk[i] > 1) {
			int j = sa[rk[i]-1];
			while (T[n-i-k] == T[n-j-k]) k++;
			h[rk[i]] = k;
		}
	}
}

int main() {
	int q;
	scanf("%s%d",S,&q);
	for (char *s = S; *s; s++)
		extend(*s - 'a');
	for (int i = 0; i < 26; i++)
		go[0][i] = 1;
	len[0] = -1;
	while (q--) {
		scanf("%s%*d%*d",T);
		n = strlen(T);
		SA(); Height();
		int x = 1, l = 0;
		long long ans = 0;
		for (int i = 0; i < n; i++) {
			int c = T[i] - 'a';
			while (!go[x][c]) l = len[x = par[x]];
			x = go[x][c];
			ans += i + 1 - std::max(++l, h[rk[n-i]]);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

评测结果