代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cctype>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for (;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 500010;
const int Base = 31;

char s[N],t[N];
uLL f[N],H[N];
map<uLL,bool>p;

uLL get1(int i,int j) {
	uLL ans = 0;
	ans = H[j] - H[i-1] * f[j-i+1];
	return ans;
}

void solve1(int len) {
	f[0] = 1;
	for (int i=1; i<=len; ++i) f[i] = f[i-1] * Base;
	for (int i=1; i<=len; ++i) H[i] = H[i-1] * Base + s[i] - 'a' + 1;
	for (int i=1; i<=len; ++i) 
		for (int j=i; j<=len; ++j) {
			uLL a = get1(i,j);
			p[get1(i,j)] = true;
		}

	int Q = read(),Ans = 0,l,r;
	while (Q--) {
		Ans = 0; 
		scanf("%s",t+1);
		scanf("%d%d",&l,&r);
		len = strlen(t+1);
		for (int i=1; i<=len; ++i) H[i] = H[i-1] * Base + t[i] - 'a' + 1;
		for (int i=1; i<=len; ++i) 
			for (int j=i; j<=len; ++j) {
				uLL a = get1(i,j);
				if (p[get1(i,j)] == 1) continue;
				else {Ans += (len - j + 1);break;}
			}
		printf("%d\n",Ans);
	}
}
int main() {
	

	
	scanf("%s",s+1);
	int len = strlen(s+1);
	solve1(len);
	return 0;
}
/*
cbamge
1
smape 1 6

bamgep
1
sbape 1 6

scbamgepe
2
sgepe 1 9
sgepe 1 9
*/

评测结果