代码

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int Q,n,l,r;
char s[23333],t[23333];
ll p[23333],h[23333],H[23333];
inline ll hash0(int i,int j){return ((h[j]-h[i-1]*p[j-i+1])%mod+mod)%mod;}
inline ll hash1(int i,int j){return ((H[j]-H[i-1]*p[j-i+1])%mod+mod)%mod;}
bool check(int i,int j){
	ll now=hash1(i,j);
	/* S[k...k+j-i],T[i...j] */
	for (int k=l;k<=n;k++) {
		int l0=k+j-i;
		if (l0<=r&&now==hash0(k,l0)) return 0;
	}
	return 1;
}
int main(){
	scanf("%s%d",s+1,&Q);
	if (Q>200) return 0;
	n=strlen(s+1);
	p[0]=1; for (int i=1;i<=n;i++) p[i]=p[i-1]*20123%mod;
	for (int i=1;i<=n;i++) h[i]=(h[i-1]*20123+s[i])%mod;
	while (Q--){
		scanf("%s%d%d",t+1,&l,&r);
		int m=strlen(t+1),ans=0;
		for (int i=1;i<=m;i++) H[i]=(H[i-1]*20123+t[i])%mod;
		for (int i=1;i<=m;i++)
			for (int j=i;j<=m;j++) ans+=check(i,j);
		printf("%d\n",ans);
	}
	return 0;
}

评测结果