代码

#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int N=500005,T=26;
int pa[N<<1],son[N<<1][T],dep[N<<1];
int cnt,last;
char Sa[N],Sb[N];
int sa[N],sb[N],lena,lenb;
inline int new_node(int step) {
	dep[++cnt]=step;
	return cnt;
}
inline void SAM(int alp) {
	int p=new_node(dep[last]+1);
	int u=last;
	while(u&&!son[u][alp])son[u][alp]=p,u=pa[u];
	if(!u)pa[p]=1;
	else {
		int v=son[u][alp];
		if(dep[v]==dep[u]+1)
			pa[p]=v;
		else {
			int nv=new_node(dep[u]+1);
			memcpy(son[nv],son[v],sizeof son[nv]);
			pa[nv]=pa[v],pa[v]=pa[p]=nv;
			while(u&&son[u][alp]==v)
				son[u][alp]=nv,u=pa[u];
		}
	}
	last=p;
}
int ts[N<<1],pos[N<<1],cont[N<<1],flag[N<<1];
inline void Sort() {
	int i;
	for(i=1;i<=cnt;i++)
		ts[i]=0;
	for(i=1;i<=cnt;i++)
		ts[dep[i]]++;
	for(i=1;i<=cnt;i++)
		ts[i]+=ts[i-1];
	for(i=1;i<=cnt;i++)
		pos[ts[dep[i]]--]=i;
}
inline void Cal() {
	int p=1,i;
	for(i=0;i<lena;i++) {
		int alp=sa[i];
		cont[son[p][alp]]++;
		p=son[p][alp];
	}
	for(i=cnt;i>=1;i--) {
		int q=pos[i];
		cont[pa[q]]+=cont[q];
	}
}
inline int calc(int x,int y) {
	return 1ll*x*(x+1)/2-1ll*y*(y+1)/2;
}
long long ans;
int f[N];
inline void solve() {
	int i;
	int temp=0,p=1;
	ans=0;
	for(i=0;i<lenb;i++) {
		int d=sb[i];
		if(son[p][d]) {
			temp++;
			p=son[p][d];
		}
		else{
			while(p&&!son[p][d])
				p=pa[p];
			if(!p)
				temp=0,p=1;
			else
				temp=dep[p]+1,p=son[p][d];
		}
		//cout<<cont[p]<<endl;	
		f[i]=temp;
	}
//	for(int i=0;i<lenb;++i)
//		cout<<f[i]<<" ";
//	cout<<endl;
	int lst=0;
	for(int i=0;i<lenb;++i)
		if(f[i+1]!=f[i]+1)
			ans+=calc(f[i],lst),lst=f[i+1]-1;
}
void init() {
	memset(flag,0,sizeof flag);
	memset(cont,0,sizeof cont);
	memset(son,0,sizeof son);
	memset(pa,0,sizeof pa);
	last=cnt=1;
}
inline void File() {
	freopen("name.in","r",stdin);
	freopen("name.out","w",stdout);
}
int main() {
	init();
	scanf("%s",Sa);
	lena=strlen(Sa);
	for(int i=0;i<lena;i++) {
		sa[i]=Sa[i]-'a';
		SAM(sa[i]);
	}
	int q;
	read(q);
	while(q--) {
		scanf("%s",Sb);
		int x,y;ans=0;
		scanf("%d%d",&x,&y);
		lenb=strlen(Sb);
		for(int i=0;i<lenb;i++)
			sb[i]=Sb[i]-'a';
		Sort();
		Cal();
		solve();
		writeln((1ll*lenb*(lenb+1)/2)-ans);
	}
}

评测结果