代码

#include <cstdio>
#include <cstring>
#include <map>

typedef long long LL;
const int N = 2000005, BAS = 137;

int n, m, Qi;
char s[N], t[N];
LL ans, H[N], h[N];
std::map<LL, int> M;

struct Sam {
	int tot, lst, tr[26][N], fa[N], dep[N];
	inline int New_(int _dep, int slink) {
		dep[++tot] = _dep; fa[tot] = slink;
		return tot;
	}	
	void Ins(int a) {
		int np = New_(dep[lst] + 1, 0), p = lst;
		lst = np;
		for (; p && !tr[a][p]; p = fa[p]) tr[a][p] = np;
		if (!p) return void(fa[np] = 1);
		int q = tr[a][p];
		if (dep[p] + 1 == dep[q]) return void(fa[np] = q);
		int y = New_(dep[p] + 1, fa[q]);
		for (int i = 0; i < 26; ++i) tr[i][y] = tr[i][q];
		fa[q] = fa[np] = y;
		for (; p && tr[a][p] == q; p = fa[p]) tr[a][p] = y;
	}
	void Clear() {
		for (int i = 1; i <= tot; ++i) {
			for (int j = 0; j < 26; ++j) tr[j][i] = 0;
			fa[i] = dep[i] = 0;
		}
		tot = lst = 1;
	}
} SA, SB;

inline LL Hash_(int l, int r) {
	return (h[r] - h[l - 1]) * H[m - l];
}

int main() {
	H[0] = 1;
	for (int i = 1; i < N; ++i) H[i] = H[i - 1] * BAS;
	
	scanf("%s", s + 1);
	n = strlen(s + 1);
	SA.Clear();
	for (int i = 1; i <= n; ++i) {
		SA.Ins(s[i] - 'a');
	}
	
	scanf("%d", &Qi);
	for (int fk; Qi; --Qi) {
		scanf("%s%d%d", t + 1, &fk, &fk);
		m = strlen(t + 1);
		SB.Clear(); M.clear(); ans = 0;
		for (int i = 1; i <= m; ++i) {
			h[i] = h[i - 1] + H[i] * t[i];
			SB.Ins(t[i] - 'a');
		}
		for (int i = 2; i <= SB.tot; ++i) {
			ans += SB.dep[i] - SB.dep[SB.fa[i]];
		}
		
		for (int i = 1; i <= m; ++i) {
			int p = 1;
			for (int j = i; j <= m; ++j) {
				int nx = t[j] - 'a';
				if (SA.tr[nx][p]) p = SA.tr[nx][p]; else break;
				LL ha = Hash_(i, j);
				if (M[ha] == 0) {
					M[ha] = 1; --ans;
				}
			}
		}
		printf("%lld\n", ans);
	}
	
	return 0;
}

评测结果