代码

#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
using namespace std;
const int N=500010;
#define int long long
int n,i,j,tot=1,slink[N*2],trans[N*2][26],endpos[N*2][2],maxlen[N*2],pre[N*2][2];
int top,fir[N*2],ne[N*4],la[N*4],to[N*4],BLOCK,q,l,r;
const int base1=233,base2=97,ha1=1e7+19,ha2=1e7+79;
char s[N],t[N];
int ans;
int HASH[10000100][2];
int newstate(int mx,int* _trans,int _slink)
{
    tot++,maxlen[tot]=mx,slink[tot]=_slink;
    if(_trans)for(int i=0;i<26;i++)trans[tot][i]=_trans[i];
    else for(int i=0;i<26;i++)trans[tot][i]=-1;
    return tot;
}
int addchar(int now,char ch,int which)
{
    int c=ch-'a',v=now;
    int NEW=newstate(maxlen[now]+1,NULL,1);
    while(v!=-1&&trans[v][c]==-1)trans[v][c]=NEW,v=slink[v];
    if(v==-1)
    {
        slink[NEW]=1;
        return NEW;
    }
    int x=trans[v][c];
    if(maxlen[v]+1==maxlen[x])
    {
        slink[NEW]=x;
        return NEW;
    }
    
    int y=newstate(maxlen[v]+1,trans[x],slink[x]);
    slink[x]=slink[NEW]=y;
    
    while(v!=-1&&trans[v][c]==x)
    {
        trans[v][c]=y;
        v=slink[v];
    }
    return NEW;
}
void add(int x,int y)
{
    top++,to[top]=y;
    if(fir[x]==0)fir[x]=top;else ne[la[x]]=top;
    la[x]=top;
}
void dfs(int x)
{
    for(int i=fir[x];i;i=ne[i])
    dfs(to[i]),endpos[x][0]+=endpos[to[i]][0],endpos[x][1]+=endpos[to[i]][1];
    endpos[x][0]+=pre[x][0],endpos[x][1]+=pre[x][1];
     
    if(endpos[x][0]==0)ans+=(maxlen[x]-maxlen[slink[x]]);
}
map<pair<int,int>,int > mp;
main()
{
	scanf("%s",s+1),n=strlen(s+1);BLOCK=700;
    memset(trans[1],-1,sizeof trans[1]);slink[1]=-1;
    int LA=1;
    for(i=1;i<=n;i++)LA=addchar(LA,s[i],0),pre[LA][0]++;
    scanf("%lld",&q);
    while(q--)
    {
    	scanf("%s",t+1);scanf("%lld%lld",&l,&r);int len=strlen(t+1);ans=0;
    	if(len<BLOCK)
//    	if(0)
    	{
    		int now;
    		for(i=1;i<=len;i++)
    		{
    			now=1;int H1=0,H2=0;
    			for(j=i;j<=len;j++)
    			{
    				H1=(H1*base1+t[j])%ha1;
    				H2=(H2*base2+t[j])%ha2;
    				if(now!=-1)now=trans[now][t[j]-'a'];
    				if(now==-1)
					{
						if(mp[make_pair(H1,H2)]==0)
						ans++,mp[make_pair(H1,H2)]=1;
						
					}
				}
			}
    		printf("%lld\n",ans);
		}else
		{
			int LA=1;
    		for(i=1;i<=len;i++)LA=addchar(LA,t[i],1),pre[LA][1]++;
    		for(i=2;i<=tot;i++)
			add(slink[i],i);

        	dfs(1);
			printf("%lld\n",ans);
			
			
			memset(fir,0,sizeof fir);
			memset(ne,0,sizeof ne);
			memset(to,0,sizeof to);
			memset(la,0,sizeof la);top=0;
			
			memset(trans,0,sizeof trans);
			memset(trans[1],-1,sizeof trans[1]);
			memset(slink,0,sizeof slink);
			memset(endpos,0,sizeof endpos);
			memset(pre,0,sizeof pre);
			tot=1;
			slink[1]=-1;
    		LA=1;
    		for(i=1;i<=n;i++)LA=addchar(LA,s[i],0),pre[LA][0]++;
		}
	}
    return 0;
}

评测结果