代码

#include<iostream>
#include<cstdio>
#include<cstring>

char S[600000],T[600000];
int n,l,r;
bool Hash1[20000000],Hash2[20000000],Hash3[20000000];

struct Trie{
	int son[100000][26],tot;
	void add_string(char *str){
		int now=1;
		int len=strlen(str);
		for (int i=0;i<len;i++){
			int s=str[i]-'a';
			if (!son[now][s]) son[now][s]=++tot;
			now=son[now][s];
		}
	}
	int query_string(char *str){
		int now=1,ans=0;
		long long hash1=1,hash2=1,hash3=1;
		int len=strlen(str);
		for (int i=0;i<len;i++){
			int s=str[i]-'a';
			hash1=(long long)(hash1+s)*65432101%18932443;
			hash2=(long long)(hash2+s)*35433131%19972681;
			hash3=(long long)(hash3+s)*21937195%16781639;
			if (son[now][s]) ans++;
			if (!son[now][s]&&Hash1[hash1]&&Hash2[hash2]&Hash3[hash3]) ans++;
			Hash1[hash1]=Hash2[hash2]=Hash3[hash3]=true;
			now=son[now][s];
		}
		return ans;
	}
}Tree;

int main(){
	scanf("%s",S);int Slen=strlen(S);
	for (int i=0;i<Slen;i++) Tree.add_string(S+i);
	Tree.tot=1; 
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%s%d%d",T,&l,&r);
		int Tlen=strlen(T);
		int Ans=0;
		memset(Hash1,0,sizeof(Hash1));
		memset(Hash2,0,sizeof(Hash2));
		memset(Hash3,0,sizeof(Hash3));
		for (int j=0;j<Tlen;j++)
			Ans+=Tree.query_string(T+j);
		printf("%d\n",(1+Tlen)*Tlen/2-Ans);
	}
}

评测结果